4448: [Scoi2015]情报传递|主席树|离线操作
程序员文章站
2023-12-25 12:25:09
可以把所有的操作离线,然后树链剖分将所有人搜集情报的时间加入到主席树中,查询的时候可以直接查询搜集情报时间≤i?C[i]?1的人的个数
时间复杂度n?log22n,空间复杂...
可以把所有的操作离线,然后树链剖分将所有人搜集情报的时间加入到主席树中,查询的时候可以直接查询搜集情报时间
时间复杂度
#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]]
推荐阅读
-
4448: [Scoi2015]情报传递|主席树|离线操作
-
php范围解析操作符(::)
-
JS的递增/递减运算符和带操作的赋值运算符的等价式_javascript技巧
-
JS脚本加载后执行相应回调函数的操作方法
-
php-求zend studio 10.1.0离线汉化包
-
PHP数组游标实现对数组的各种操作详解,php数组游标详解_PHP教程
-
js封装的textarea操作方法集合(兼容很好)_javascript技巧
-
用Mootools获得操作索引的两种方法分享_Mootools
-
EasyUI DataGrid结合ThinkPHP实现增删改查操作初学者_html/css_WEB-ITnose
-
php获取服务器操作系统相关信息的方法