可以把所有的操作離線，然後樹鏈剖分將所有人搜集情報的時間加入到主席樹中，查詢的時候可以直接查詢搜集情報時間≤i?C[i]?1的人的個數 時間復雜度n?log22n，空間復雜度n?log2n
#include #include #include #include #include #include #include #include #include #include #define ll long long #define N 202020 using namespace std; int sc() { int i=0,f=1; char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar(); return i*f; } int opt[N],X[N],Y[N],C[N]; int sum[N*20],ch[N*20][2],tim[N],root[N]; int fa[N],top[N],size[N],deep[N],S[N],wh[N]; int head[N],nxt[N],lst[N]; int n,m,tot,cnt,num; void insert(int x,int y) { lst[++tot]=y;nxt[tot]=head[x];head[x]=tot; } void dfs(int x) { size[x]=1; for(int i=head[x];i;i=nxt[i]) { deep[lst[i]]=deep[x]+1; fa[lst[i]]=x; dfs(lst[i]); size[x]+=size[lst[i]]; } } void _dfs(int x,int htp) { int k=0;S[x]=++cnt;top[x]=htp;wh[cnt]=x; for(int i=head[x];i;i=nxt[i]) if(size[lst[i]]>size[k])k=lst[i]; if(!k)return ;_dfs(k,htp); for(int i=head[x];i;i=nxt[i]) if(lst[i]!=k)_dfs(lst[i],lst[i]); } void add(int pre,int &x,int l,int r,int v) { if(!x)x=++num; sum[x]=sum[pre]+1; if(l==r)return; int mid=l+r>>1; if(v<=mid) ch[x][1]=ch[pre][1], add(ch[pre][0],ch[x][0],l,mid,v); else ch[x][0]=ch[pre][0], add(ch[pre][1],ch[x][1],mid+1,r,v); } int query(int x,int y,int c) { int L=root[x-1],R=root[y],l=1,r=m,res=0; while(l!=r) { int mid=l+r>>1; if(c<=mid) L=ch[L][0],R=ch[R][0],r=mid; else res+=sum[ch[R][0]]-sum[ch[L][0]], L=ch[L][1],R=ch[R][1],l=mid+1; } res+=(c>=l?sum[R]-sum[L]:0); return res; } void solve(int x,int y,int c) { int sum=0,res=deep[x]+deep[y]; while(top[x]!=top[y]) { if(deep[top[x]]
復化梯形 將積分區間[a,b]劃分n等分，步長，求積節
c++ list, vector, map, set 區別與
HDU-4419-Colourful Rectangle(線
Prime Ring Problem（杭電1016）（DFS
C++中的操作符 Last Edit
hdu 2604 Queuing£¨¾ØÕóÓÅ»¯µÝÍÆ
