首页 > 代码库 > bzoj4419[SHOI2013]发微博
bzoj4419[SHOI2013]发微博
题意:给你一个初始没有边,点权均为0的无向图,三种操作:加边,删边,选择一个点将当前与之相邻的点(不包括自身)的点权+1,询问最后所有点的点权。
据说正解是set维护每个人的朋友,然后考虑每次加边、删边对答案的贡献......但作为脑子有坑的选手,我搞出了一个动态开点线段树....首先离线,分别考虑每条边对答案的贡献。不妨分别考虑这条边存在的每一个时间区间。那么我们只要知道这个时间区间中两个端点各进行了几次点权增加(发微博)操作就可以更新两边的答案。考虑对每一个点开一棵线段树,如果这个点在第i个操作中发了一条微博就把下标为i处+1,查询的时候线段树区间查询即可。直接建的空间复杂度n*mlogm会TLE+MLE,所以动态开点,每次修改操作建一条链,总的空间复杂度mlogm。用map存了一下边所以很慢明明是线段树常数炸天
注意m次操作后没有被删除的边也要更新答案,WA了一发。
#include<cstdio> #include<map> using namespace std; const int maxn=200005,maxm=500005; int n,m; struct node{ int sum; node *lch,*rch; node(){ sum=0; lch=rch=0; } }t[maxm*20];int cnt=0; node *root[maxn]; map<long long,int> dict; void Insert(node *&rt,int k,int l,int r){ if(rt==0){ ++cnt;rt=t+cnt; } if(l==r){ rt->sum++; return; } int mid=(l+r)>>1; if(k<=mid)Insert(rt->lch,k,l,mid); else Insert(rt->rch,k,mid+1,r); rt->sum=0; if(rt->lch)rt->sum+=rt->lch->sum; if(rt->rch)rt->sum+=rt->rch->sum; } int ql,qr,ans; void query(node *rt,int l,int r){ if(rt==0)return; if(ql<=l&&r<=qr){ ans+=rt->sum; return; } int mid=(l+r)>>1; if(ql<=mid)query(rt->lch,l,mid); if(qr>mid)query(rt->rch,mid+1,r); } int u[maxm],v[maxm],from[maxm],to[maxm];int tot=0; int res[maxn]; int main(){ scanf("%d%d",&n,&m); char buf[2]; int a,b; for(int i=1;i<=m;++i){ scanf("%s",buf); if(buf[0]==‘!‘){ scanf("%d",&a); Insert(root[a],i,1,m); }else if(buf[0]==‘+‘){ scanf("%d%d",&a,&b); if(a>b)swap(a,b); dict[(a-1)*1LL*n+b]=i; }else{ scanf("%d%d",&a,&b); if(a>b)swap(a,b); ++tot; u[tot]=a;v[tot]=b; from[tot]=dict[(a-1)*1LL*n+b]; dict.erase((a-1)*1LL*n+b); to[tot]=i; } } for(int i=1;i<=tot;++i){ ql=from[i];qr=to[i]; ans=0; query(root[v[i]],1,m);res[u[i]]+=ans; ans=0; query(root[u[i]],1,m);res[v[i]]+=ans; } for(map<long long,int>::iterator pt=dict.begin();pt!=dict.end();++pt){ ql=pt->second;qr=m; a=(pt->first-1)/n+1;b=(pt->first)%n; if(b==0)b=n; ans=0; query(root[a],1,m);res[b]+=ans; ans=0; query(root[b],1,m);res[a]+=ans; } for(int i=1;i<=n;++i)printf("%d%c",res[i],(i==n)?‘\n‘:‘ ‘); }
bzoj4419[SHOI2013]发微博
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。