正题

      Portal

      这题发现总的元素数量不超过M，所以我们可以对一个集合内的元素数量来根号分治。

      当询问的时，暴力维护每一个权值以位置为关键字的线段树（动态开点），这部分的时间复杂度是。

      当询问的时，我们对于这些特殊的集合维护一个以位置为关键字的树状数组，每个位置的权值就是该集合与特殊集合的交集，更新显然，每次查询直接差分前缀和即可。这部分的时间复杂度为。

      这两个都是最坏时间复杂度，当时，有最小时间复杂度。

      但是为了避免麻烦，我们可以直接设为。就保证了特殊集合最多只有1000个。

      发现空间上还是爆炸，直接考虑把空间开小一点，或者选择vector，因为实际上的特殊集合并没有那么多。

      反正我空间是卡过去的，时间上没有问题。

#include<cmath>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define lowbit(x) (x&(-x))
using namespace std;const int N=40010,M=200010,A=1000000;
int n,m,bound,tot,num;
vector<int> S[N],V[A+1];
bool tf[501][A+1];
int root[A+1],id[N];
int t[M*16],ls[M*16],rs[M*16];
int sum[501][N];void insert(int&now,int d,int l,int r){if(now==0) now=++num;t[now]++;if(l==r) return ;int mid=(l+r)/2;if(d<=mid) insert(ls[now],d,l,mid);else insert(rs[now],d,mid+1,r);
}void add(int*now,int x,int t){while(x<=n){now[x]+=t;x+=lowbit(x);}return ;
}int get_tot(int now,int x,int y,int l,int r){if(x==l && y==r) return t[now];int mid=(l+r)/2;if(y<=mid) return get_tot(ls[now],x,y,l,mid);else if(mid<x) return get_tot(rs[now],x,y,mid+1,r);else return get_tot(ls[now],x,mid,l,mid)+get_tot(rs[now],mid+1,y,mid+1,r);
}int get_sum(int*now,int x){long long tot=0;while(x){tot+=now[x];x-=lowbit(x);}return tot;
}int main(){char c[2];int x,y,l;scanf("%d %d",&n,&m);bound=ceil(m/1000.0);while(m--){scanf("%s %d %d",c,&x,&y);if(c[0]=='I'){S[x].push_back(y);if(S[x].size()==bound){id[x]=++tot;for(int j=0;j<S[x].size();j++) tf[id[x]][S[x][j]]=true;for(int j=1;j<=n;j++) {int t=0;for(int k=0;k<S[j].size();k++) if(tf[id[x]][S[j][k]]) t+=S[j][k];if(t){add(sum[id[x]],j,t);if(j!=x && id[j] && tf[id[j]][y]) add(sum[id[j]],x,y);}}}else if(S[x].size()>bound){tf[id[x]][y]=true;for(int j=0;j<V[y].size();j++){add(sum[id[x]],V[y][j],y);if(id[V[y][j]]) add(sum[id[V[y][j]]],x,y);}add(sum[id[x]],x,y);}else if(S[x].size()<bound) for(int j=1;j<=tot;j++) if(tf[j][y]) add(sum[j],x,y);insert(root[y],x,1,n);V[y].push_back(x);}else{scanf("%d",&l);if(S[x].size()<bound){int tot=0;for(int j=0;j<S[x].size();j++)tot+=get_tot(root[S[x][j]],y,l,1,n)*S[x][j];printf("%d\n",tot);}else if(S[x].size()>=bound) printf("%d\n",get_sum(sum[id[x]],l)-get_sum(sum[id[x]],y-1));}}
}