//下面内容请选择性阅读
一些胡乱的感受：
抽 象 主 义 解 题
充分让我认识到了我的码力有多么弱
我真是对力量一无所知
*你妈的，随便伤害无辜少年*
维护维护维护维护维护维护
猫不仅喜欢上树，还喜欢上数据结构
sto immortalco orz
— —好了，还有什么人要提问
— —我要！
— —什么？
— —我写乱搞淦猫式上树树上问题，好吗
— —好！
*激烈的调试大赛*
//正文开始了
线段树神仙题
什么，我的题解？去看i207M的吧
1 // luogu-judger-enable-o2 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=4e6+60,inf=1e9; 7 int n,m,q,t1,t2,t3,t4,typ,len[N*4]; 8 struct a 9 { 10 int arr[N*4]; 11 int* operator[] (int x) 12 { 13 return arr+x*m; 14 } 15 }mapp,upp,low,mat; 16 struct Mono_queue 17 { 18 int f,b,que[N]; 19 int* arr; 20 int Size(){return b-f+1;} 21 int Front(){return arr[que[f]];} 22 void Init(int* ar){f=0,b=-1,arr=ar;} 23 void Pop(int x){while(f<=b&&que[f]<=x) f++;} 24 void Push(int x){while(f<=b&&arr[x]<=arr[que[b]]) b--;que[++b]=x;} 25 }; 26 int Calc(int x,int y,int l,int r) 27 { 28 int ret=0; 29 static Mono_queue q1,q2; 30 q1.Init(upp[x]),q2.Init(low[y]); 31 for(int b=l,f=l;b<=r;b++) 32 { 33 q1.Push(b),q2.Push(b); 34 while(q1.Size()&&q2.Size()&&f<=b&&q1.Front()+q2.Front()<b-f+1) 35 q1.Pop(f),q2.Pop(f),f++; 36 ret=max(ret,b-f+1); 37 } 38 int *a1=upp[x],*a2=upp[y]; 39 for(int i=l;i<=r;i++) a1[i]=(a2[i]==len[y])?a1[i]+len[y]:a2[i]; 40 len[x]+=len[y]; 41 return ret; 42 } 43 void Pushup(int p,int x,int y) 44 { 45 static Mono_queue q1,q2; 46 q1.Init(upp[x]),q2.Init(low[y]); 47 int *a1=mat[p],*a2=mat[x],*a3=mat[y]; 48 for(int b=1,f=1;b<=m;b++) 49 { 50 q1.Push(b),q2.Push(b); 51 while(q1.Size()&&q2.Size()&&f<=b&&q1.Front()+q2.Front()<b-f+1) 52 q1.Pop(f),q2.Pop(f),f++; 53 a1[b]=max(b-f+1,max(a2[b],a3[b])); 54 } 55 a1=upp[p],a2=upp[x],a3=upp[y]; 56 for(int i=1;i<=m;i++) a1[i]=(a3[i]==len[y])?a2[i]+len[y]:a3[i]; 57 a1=low[p],a2=low[x],a3=low[y]; 58 for(int i=1;i<=m;i++) a1[i]=(a2[i]==len[x])?a3[i]+len[x]:a2[i]; 59 len[p]=len[x]+len[y]; 60 } 61 void Create(int nde,int l,int r) 62 { 63 if(l==r) 64 { 65 len[nde]=1; 66 for(int i=1;i<=m;i++) 67 upp[nde][i]=low[nde][i]=mapp[l][i]; 68 } 69 else 70 { 71 int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; 72 Create(ls,l,mid),Create(rs,mid+1,r),Pushup(nde,ls,rs); 73 } 74 } 75 void Change(int nde,int l,int r,int pos,int tsk) 76 { 77 if(l==r) 78 mapp[l][tsk]^=1,upp[nde][tsk]=low[nde][tsk]=mapp[l][tsk]; 79 else 80 { 81 int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; 82 if(pos<=mid) Change(ls,l,mid,pos,tsk); 83 else Change(rs,mid+1,r,pos,tsk); Pushup(nde,ls,rs); 84 } 85 } 86 int Query(int nde,int l,int r,int nl,int nr,int ml,int mr) 87 { 88 if(l>=nl&&r<=nr) 89 { 90 int ret=Calc(0,nde,ml,mr); 91 int *arr=mat[nde]; 92 for(int i=ml;i<=mr;i++) 93 ret=max(ret,min(arr[i],i-ml+1)); 94 return ret; 95 } 96 else 97 { 98 int mid=(l+r)/2,ls=2*nde,rs=2*nde+1,ret=0; 99 if(mid>=nl) ret=max(ret,Query(ls,l,mid,nl,nr,ml,mr)); 100 if(mid<nr) ret=max(ret,Query(rs,mid+1,r,nl,nr,ml,mr)); 101 return ret; 102 } 103 } 104 int main() 105 { 106 scanf("%d%d%d",&n,&m,&q); 107 for(int i=1;i<=n;i++) 108 for(int j=1;j<=m;j++) 109 scanf("%d",&mapp[i][j]); 110 Create(1,1,n); 111 while(q--) 112 { 113 scanf("%d%d%d",&typ,&t1,&t2); 114 if(!typ) Change(1,1,n,t1,t2); 115 else 116 { 117 scanf("%d%d",&t3,&t4); 118 for(int i=1;i<=m;i++) upp[0][i]=0; len[0]=0; 119 printf("%d ",Query(1,1,n,t1,t3,t2,t4)); 120 } 121 } 122 return 0; 123 }
清华集训 2016 数据交互
两条链有交当且仅当有一条链的LCA在另一条链上，动态DP
被卡常了，卡了一会，没卡过去，懒得卡了
什么，我的题解？去看这位神仙的吧
1 #include<set> 2 #include<cstdio> 3 #include<cctype> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 const int N=100005; 8 int n,m,t1,t2,rd,cnt,tot; 9 long long laz[4*N],val[4*N]; char str[10]; 10 int p[N],noww[2*N],goal[2*N],u[N],v[N],w[N],endp[N]; 11 int siz[N],far[N],dep[N],imp[N],top[N],dfn[N],ori[N]; 12 multiset<long long> st,ss[N]; 13 struct a 14 { 15 long long ll,rr,mx,sum; 16 }seg[4*N]; 17 a operator + (a x,a y) 18 { 19 a ret; 20 ret.ll=max(x.ll,x.sum+y.ll); 21 ret.rr=max(y.rr,y.sum+x.rr); 22 ret.mx=max(max(x.mx,y.mx),x.rr+y.ll); 23 ret.sum=x.sum+y.sum; return ret; 24 } 25 void Read(int &x) 26 { 27 x=0; char ch=getchar(); 28 while(!isdigit(ch)) 29 ch=getchar(); 30 while(isdigit(ch)) 31 x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 32 } 33 void Link(int f,int t) 34 { 35 noww[++cnt]=p[f]; 36 goal[cnt]=t,p[f]=cnt; 37 noww[++cnt]=p[t]; 38 goal[cnt]=f,p[t]=cnt; 39 } 40 void DFS(int nde,int fth,int dth) 41 { 42 int tmp=0; 43 siz[nde]=1,far[nde]=fth,dep[nde]=dth; 44 for(int i=p[nde];i;i=noww[i]) 45 if(goal[i]!=fth) 46 { 47 DFS(goal[i],nde,dth+1); 48 siz[nde]+=siz[goal[i]]; 49 if(siz[goal[i]]>tmp) 50 tmp=siz[goal[i]],imp[nde]=goal[i]; 51 } 52 } 53 void Mark(int nde,int tpp) 54 { 55 top[nde]=tpp,dfn[nde]=++tot; 56 endp[nde]=dfn[nde],ori[tot]=nde; 57 if(imp[nde]) 58 { 59 Mark(imp[nde],tpp); 60 endp[nde]=endp[imp[nde]]; 61 for(int i=p[nde];i;i=noww[i]) 62 if(goal[i]!=far[nde]&&goal[i]!=imp[nde]) 63 ss[nde].insert(0),Mark(goal[i],goal[i]); 64 } 65 else st.insert(0); 66 } 67 int LCA(int x,int y) 68 { 69 while(top[x]!=top[y]) 70 { 71 if(dep[top[x]]<dep[top[y]]) 72 swap(x,y); x=far[top[x]]; 73 } 74 return dep[x]<dep[y]?x:y; 75 } 76 void Release(int nde) 77 { 78 if(laz[nde]) 79 { 80 int ls=2*nde,rs=2*nde+1,lz=laz[nde]; 81 laz[ls]+=lz,seg[ls].rr+=lz,seg[ls].mx+=lz; 82 laz[rs]+=lz,seg[rs].rr+=lz,seg[rs].mx+=lz; 83 laz[nde]=0; 84 } 85 } 86 a Query(int nde,int l,int r,int ll,int rr) 87 { 88 if(l>=ll&&r<=rr) 89 return seg[nde]; 90 else 91 { 92 int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; Release(nde); 93 if(mid>=rr) return Query(ls,l,mid,ll,rr); 94 else if(mid<ll) return Query(rs,mid+1,r,ll,rr); 95 else return Query(ls,l,mid,ll,rr)+Query(rs,mid+1,r,ll,rr); 96 } 97 } 98 void Ex(int nde,int l,int r,int pos,long long tsk) 99 { 100 if(l==r) 101 { 102 int orn=ori[l]; long long ret=0; 103 val[nde]+=tsk,seg[nde].sum=val[nde]; 104 multiset<long long> ::iterator it=ss[orn].end(); 105 if(ss[orn].size()>=1) ret+=*(--it); 106 seg[nde].ll=val[nde]+ret,seg[nde].rr=val[nde]+ret+laz[nde]; 107 if(ss[orn].size()>=2) ret+=*(--it); 108 seg[nde].mx=val[nde]+ret+laz[nde]; 109 } 110 else 111 { 112 int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; Release(nde); 113 if(pos<=mid) Ex(ls,l,mid,pos,tsk); 114 else Ex(rs,mid+1,r,pos,tsk); seg[nde]=seg[ls]+seg[rs]; 115 } 116 } 117 void Exc(int nde,int l,int r,int ll,int rr,int tsk) 118 { 119 if(l>rr||r<ll) 120 return; 121 else if(l>=ll&&r<=rr) 122 seg[nde].rr+=tsk,seg[nde].mx+=tsk,laz[nde]+=tsk; 123 else 124 { 125 int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; Release(nde); 126 Exc(ls,l,mid,ll,rr,tsk),Exc(rs,mid+1,r,ll,rr,tsk); 127 seg[nde]=seg[ls]+seg[rs]; 128 } 129 } 130 void Modify(int nde,long long val,int lca,int tsk) 131 { 132 while(nde) 133 { 134 int l=lca?max(dfn[top[nde]],dfn[lca]+1):n+1; 135 int r=dfn[nde],nxt=far[top[nde]]; 136 if(nxt) 137 { 138 a x=Query(1,1,n,dfn[top[nxt]],endp[nxt]); 139 st.erase(st.lower_bound(x.mx)); 140 ss[nxt].erase(ss[nxt].lower_bound(val)),val=x.ll; 141 } 142 if(l<=r) 143 { 144 st.erase(st.lower_bound(Query(1,1,n,dfn[top[nde]],endp[nde]).mx)); 145 Exc(1,1,n,l,r,tsk),st.insert(Query(1,1,n,dfn[top[nde]],endp[nde]).mx); 146 } 147 if(nxt) 148 { 149 ss[nxt].insert(Query(1,1,n,dfn[top[nde]],endp[nde]).ll); 150 Ex(1,1,n,dfn[nxt],0),st.insert(Query(1,1,n,dfn[top[nxt]],endp[nxt]).mx); 151 } 152 nde=nxt; 153 } 154 } 155 void Change(int u,int v,int w) 156 { 157 int lca=LCA(u,v); 158 Modify(u,Query(1,1,n,dfn[top[u]],endp[u]).ll,lca,w); 159 Modify(v,Query(1,1,n,dfn[top[v]],endp[v]).ll,lca,w); 160 a x=Query(1,1,n,dfn[top[lca]],endp[lca]); 161 st.erase(st.lower_bound(x.mx)),Ex(1,1,n,dfn[lca],w); 162 st.insert(Query(1,1,n,dfn[top[lca]],endp[lca]).mx); 163 Modify(lca,x.ll,0,0); 164 } 165 int main() 166 { 167 Read(n),Read(m); 168 for(int i=1;i<n;i++) Read(t1),Read(t2),Link(t1,t2); 169 DFS(1,0,1),Mark(1,1); 170 for(int i=1;i<=m;i++) 171 { 172 scanf("%s",str); 173 if(str[0]=='+') 174 { 175 Read(u[i]),Read(v[i]),Read(w[i]); 176 Change(u[i],v[i],w[i]); 177 } 178 else 179 Read(rd),Change(u[rd],v[rd],-w[rd]); 180 printf("%lld ",*st.rbegin()); 181 } 182 return 0; 183 }
UOJ #207 共价大爷游长沙
日，发现自己的LCT写的又是假的
学习了LCT维护子树信息：记录一个所有轻儿子的信息合并进去，具体来说要改改Access和Link
一条路径被所有路径经过，当前仅当以一个端点为根时，所有路径的端点都恰好有一个在另一个的子树中
我们每次把两个端点异或一个随机数，同时记录所有随机数的全集异或和，每次查询子树里异或和即可
1 #include<cstdio> 2 #include<cctype> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=100005,M=300005; 7 int n,m,t1,t2,t3,t4,typ,cnt,tot,fafa; 8 int fth[N],son[N][2],rev[N],stk[N]; 9 int val[N],xors[N],lits[N],mem1[M]; 10 pair<int,int> mem2[M]; 11 void Read(int &x) 12 { 13 x=0; char ch=getchar(); 14 while(!isdigit(ch)) 15 ch=getchar(); 16 while(isdigit(ch)) 17 x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); 18 } 19 void Write(int x) 20 { 21 if(x>9) Write(x/10); 22 putchar(x%10^48); 23 } 24 int Rand() 25 { 26 return 1ll*rand()*rand()*rand()%2147483647; 27 } 28 void Pushup(int nde) 29 { 30 int lson=son[nde][0],rson=son[nde][1]; 31 xors[nde]=xors[lson]^xors[rson]^val[nde]^lits[nde]; 32 } 33 void Release(int nde) 34 { 35 if(rev[nde]) 36 { 37 int &lson=son[nde][0],&rson=son[nde][1]; 38 rev[lson]^=1,rev[rson]^=1,rev[nde]^=1; 39 swap(lson,rson); 40 } 41 } 42 bool Nottop(int nde) 43 { 44 int fa=fth[nde]; 45 return son[fa][0]==nde||son[fa][1]==nde; 46 } 47 void Rotate(int nde) 48 { 49 int fa=fth[nde],gr=fth[fa],isl=nde==son[fa][0]; 50 if(Nottop(fa)) son[gr][fa==son[gr][1]]=nde; 51 fth[nde]=gr,fth[fa]=nde,fth[son[nde][isl]]=fa; 52 son[fa][isl^1]=son[nde][isl],son[nde][isl]=fa; 53 Pushup(fa),Pushup(nde); 54 } 55 void Splay(int nde) 56 { 57 int top=1; stk[top]=nde; 58 for(int i=nde;Nottop(i);i=fth[i]) 59 stk[++top]=fth[i]; 60 while(top) Release(stk[top--]); 61 while(Nottop(nde)) 62 { 63 int fa=fth[nde],gr=fth[fa]; 64 if(Nottop(fa)) 65 Rotate(((son[fa][0]==nde)==(son[gr][0]==fa))?fa:nde); 66 Rotate(nde); 67 } 68 Pushup(nde); 69 } 70 void Access(int nde) 71 { 72 int lst=0,mem=nde; 73 while(nde) 74 { 75 Splay(nde); 76 lits[nde]^=xors[son[nde][1]]; 77 lits[nde]^=xors[son[nde][1]=lst]; 78 Pushup(nde),lst=nde,nde=fth[nde]; 79 } 80 Splay(mem); 81 } 82 void Turnroot(int nde) 83 { 84 Access(nde),rev[nde]^=1; 85 } 86 int Getroot(int nde) 87 { 88 Access(nde); 89 while(son[nde][0]) 90 nde=son[nde][0]; 91 Splay(nde); 92 return nde; 93 } 94 void Split(int x,int y) 95 { 96 Turnroot(x),Access(y); 97 } 98 void Link(int x,int y) 99 { 100 Split(x,y),fth[x]=y,lits[y]^=xors[x],Pushup(y); 101 } 102 void Cut(int x,int y) 103 { 104 Split(x,y),fth[x]=son[y][0]=0,Pushup(y); 105 } 106 int Query(int x,int y) 107 { 108 Cut(x,y),Access(y); 109 int ret=xors[y]; 110 Link(x,y); 111 return ret; 112 } 113 void Change(int nde,int tsk) 114 { 115 Access(nde),val[nde]^=tsk,Pushup(nde); 116 } 117 int main() 118 { 119 srand(20020513); 120 Read(fafa),Read(n),Read(m); 121 for(int i=1;i<n;i++) 122 Read(t1),Read(t2),Link(t1,t2); 123 while(m--) 124 { 125 Read(typ); 126 if(typ==1) 127 { 128 Read(t1),Read(t2),Read(t3),Read(t4); 129 Cut(t1,t2),Link(t3,t4); 130 } 131 else if(typ==2) 132 { 133 Read(t1),Read(t2),t3=Rand(); 134 Change(t1,t3),Change(t2,t3); 135 tot^=t3,mem1[++cnt]=t3,mem2[cnt]=make_pair(t1,t2); 136 } 137 else if(typ==3) 138 { 139 Read(t1),tot^=mem1[t1]; 140 Change(mem2[t1].first,mem1[t1]); 141 Change(mem2[t1].second,mem1[t1]); 142 } 143 else 144 { 145 Read(t1),Read(t2); 146 Query(t1,t2)==tot?puts("YES"):puts("NO"); 147 } 148 } 149 return 0; 150 }
PA 2014 Fiolki
重构树，把所有步骤按时间连到虚点上，然后逆着扫求LCA，这样LCA深度越大的反应越早发生，模拟即可
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=400005,M=500005; 6 struct a{int x,y,d,id;}sol[M]; 7 int n,m,k,t1,t2,cnt,tot; long long ans; 8 int siz[N],anc[N],dep[N],imp[N],top[N]; 9 int p[N],noww[N<<1],goal[N<<1],bel[N],aset[N],g[N]; 10 bool cmp(a x,a y) 11 { 12 return x.d==y.d?x.id<y.id:x.d>y.d; 13 } 14 int Finda(int x) 15 { 16 return aset[x]==x?x:aset[x]=Finda(aset[x]); 17 } 18 void Link(int f,int t) 19 { 20 noww[++cnt]=p[f]; 21 goal[cnt]=t,p[f]=cnt; 22 noww[++cnt]=p[t]; 23 goal[cnt]=f,p[t]=cnt; 24 } 25 void DFS(int nde,int fth,int dth) 26 { 27 int tmp=0; 28 siz[nde]=1,anc[nde]=fth,dep[nde]=dth; 29 for(int i=p[nde];i;i=noww[i]) 30 if(goal[i]!=fth) 31 { 32 DFS(goal[i],nde,dth+1); 33 siz[nde]+=siz[goal[i]]; 34 if(siz[goal[i]]>tmp) 35 tmp=siz[goal[i]],imp[nde]=goal[i]; 36 } 37 } 38 void MARK(int nde,int tpp) 39 { 40 top[nde]=tpp; 41 if(imp[nde]) 42 { 43 MARK(imp[nde],tpp); 44 for(int i=p[nde];i;i=noww[i]) 45 if(goal[i]!=anc[nde]&&goal[i]!=imp[nde]) 46 MARK(goal[i],goal[i]); 47 } 48 } 49 int LCA(int x,int y) 50 { 51 while(top[x]!=top[y]) 52 { 53 if(dep[top[x]]<dep[top[y]]) 54 swap(x,y); x=anc[top[x]]; 55 } 56 return dep[x]<dep[y]?x:y; 57 } 58 int main () 59 { 60 scanf("%d%d%d",&n,&m,&k); 61 for(int i=1;i<=n;i++) 62 scanf("%d",&g[i]),bel[i]=i,aset[i]=i; 63 for(int i=1;i<=m;i++) 64 { 65 scanf("%d%d",&t1,&t2); 66 Link(bel[t1],i+n),Link(bel[t2],i+n); 67 bel[t2]=i+n,aset[Finda(t1)]=Finda(t2); 68 } 69 for(int i=n+m;i;i--) 70 if(!siz[i]) DFS(i,0,1),MARK(i,i); 71 for(int i=1;i<=k;i++) 72 { 73 scanf("%d%d",&t1,&t2); 74 if(Finda(t1)==Finda(t2)) 75 sol[++tot]=(a){t1,t2,dep[LCA(t1,t2)],i}; 76 } 77 sort(sol+1,sol+1+tot,cmp); 78 for(int i=1;i<=tot;i++) 79 { 80 int tx=sol[i].x,ty=sol[i].y,mn=min(g[tx],g[ty]); 81 g[tx]-=mn,g[ty]-=mn,ans+=2*mn; 82 } 83 printf("%lld",ans); 84 return 0; 85 }
PA 2014 Druzyny
线线线段段段树树树题
什么，我的题解？去看这位神仙的吧
卡时空好题，加上BZOJ的评测机加持，刺激
我这份代码卡着时空过的，如有需要请自行使用快读替换scanf等操作
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=1e6+10,M=4e6+20; 6 const int inf=1e9,mod=1e9+7; 7 int n,f,b,p,c[N],d[N],que[N],lpt[N],maxc[M]; 8 struct a 9 { 10 int opt,val; 11 }dp[N],seg[M],laz[M]; 12 a Re(const a &x){return (a){x.opt+1,x.val};} 13 void Add(int &x,int y){x+=y;if(x>=mod) x-=mod;} 14 a operator + (a x,a y) 15 { 16 if(x.opt!=y.opt) return x.opt>y.opt?x:y; 17 else {Add(x.val,y.val); return x;} 18 } 19 void Create2(int nde,int l,int r) 20 { 21 if(l==r) 22 maxc[nde]=l; 23 else 24 { 25 int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; 26 Create2(ls,l,mid),Create2(rs,mid+1,r); 27 maxc[nde]=(c[maxc[ls]]<c[maxc[rs]])?maxc[rs]:maxc[ls]; 28 } 29 } 30 int Query2(int nde,int l,int r,int ll,int rr) 31 { 32 if(l>rr||r<ll) 33 return 0; 34 else if(l>=ll&&r<=rr) 35 return maxc[nde]; 36 else 37 { 38 int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; 39 int r1=Query2(ls,l,mid,ll,rr); 40 int r2=Query2(rs,mid+1,r,ll,rr); 41 return c[r1]<c[r2]?r2:r1; 42 } 43 } 44 void Create3(int nde,int l,int r) 45 { 46 if(l==r) 47 seg[nde]=dp[l],laz[nde]=(a){-inf,0}; 48 else 49 { 50 int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; 51 Create3(ls,l,mid),Create3(rs,mid+1,r); 52 seg[nde]=seg[ls]+seg[rs],laz[nde]=laz[ls]+laz[rs]; 53 } 54 } 55 void Change3(int nde,int l,int r,int pos,a tsk) 56 { 57 if(l==r) 58 seg[nde]=tsk; 59 else 60 { 61 int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; 62 if(pos<=mid) Change3(ls,l,mid,pos,tsk); 63 else Change3(rs,mid+1,r,pos,tsk); 64 seg[nde]=seg[ls]+seg[rs]; 65 } 66 } 67 void Add3(int nde,int l,int r,int ll,int rr,a tsk) 68 { 69 if(l>rr||r<ll) 70 return ; 71 else if(l>=ll&&r<=rr) 72 laz[nde]=laz[nde]+tsk; 73 else 74 { 75 int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; 76 Add3(ls,l,mid,ll,rr,tsk),Add3(rs,mid+1,r,ll,rr,tsk); 77 } 78 } 79 a Query3(int nde,int l,int r,int pos) 80 { 81 a ret=(a){-inf,0}; 82 while(true) 83 { 84 ret=ret+laz[nde]; 85 if(l==r) return ret; 86 int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; 87 if(pos<=mid) nde=ls,r=mid; else nde=rs,l=mid+1; 88 } 89 return ret; 90 } 91 a Query4(int nde,int l,int r,int ll,int rr) 92 { 93 if(l>rr||r<ll) 94 return (a){-inf,0}; 95 else if(l>=ll&&r<=rr) 96 return seg[nde]; 97 else 98 { 99 int mid=(l+r)/2,ls=2*nde,rs=2*nde+1; 100 return Query4(ls,l,mid,ll,rr)+Query4(rs,mid+1,r,ll,rr); 101 } 102 } 103 int BS(int l,int r,int x) 104 { 105 int ret=0; 106 while(l<=r) 107 { 108 int mid=(l+r)/2; 109 if(lpt[mid]<=x) l=mid+1,ret=mid; 110 else r=mid-1; 111 } 112 return ret; 113 } 114 void Solve(int l,int r,int k) 115 { 116 int mid=max(k,l+c[k]),ll=max(l,lpt[mid]),rr=min(k-1,mid-c[k]); 117 if(r<mid||k<=ll) return ; 118 a qry=Query4(1,0,n,ll,rr); 119 while(ll<=l&&mid<=r) 120 { 121 if(k-1<=rr) 122 { 123 int newr=BS(mid,r,l); 124 Add3(1,0,n,mid,newr,Re(qry)),mid=newr+1; 125 break; 126 } 127 dp[mid]=dp[mid]+Re(qry); 128 qry=qry+dp[++rr],ll=max(ll,lpt[++mid]); 129 } 130 while(mid<=r) 131 { 132 ll=lpt[mid],rr=min(k-1,mid-c[k]); 133 if(k<ll) return ; 134 a qur=Query4(1,0,n,ll,rr); 135 qur.opt++,dp[mid]=dp[mid]+qur,mid++; 136 } 137 } 138 void Divide(int l,int r) 139 { 140 if(l>r) return; 141 else if(l==r) 142 { 143 dp[l]=dp[l]+Query3(1,0,n,l); 144 Change3(1,0,n,l,dp[l]); return ; 145 } 146 else 147 { 148 int mid=Query2(1,0,n,l+1,r); 149 Divide(l,mid-1),Solve(l,r,mid),Divide(mid,r); 150 } 151 } 152 int main() 153 { 154 scanf("%d",&n),f=0,b=-1; 155 for(int i=1;i<=n;i++) 156 scanf("%d%d",&c[i],&d[i]); 157 for(int i=1;i<=n;dp[i].opt=-inf,i++) 158 { 159 lpt[i]=lpt[i-1]; 160 while(f<=b&&d[i]<=d[que[b]]) b--; 161 que[++b]=i; 162 while(f<=b&&d[que[f]]+lpt[i]<i) 163 f+=que[f]==lpt[i]+1,lpt[i]++; 164 } 165 dp[0].val=1; 166 Create2(1,0,n),Create3(1,0,n),Divide(0,n); 167 (dp[n].opt>0)?printf("%d %d",dp[n].opt,dp[n].val):printf("NIE"); 168 return 0; 169 }
SCOI 2016 萌萌哒
显然是并查集数联通块数cnt，然后答案是$9*10^{cnt-1}$(最高位填1-9，剩下的填0-9)
ST表的思想，令$aset[i][j]$表示$[i,i+2^j-1]$这一块的连通性，递归合并，注意剪枝
1 #include<cmath> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=100005,K=19,mod=1e9+7; 7 int n,m,l1,l2,t1,t2,t3,t4,len,ans,aset[K][N]; 8 int Qpow(int x,int k) 9 { 10 if(k==1) return x; 11 int tmp=Qpow(x,k/2); 12 return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod; 13 } 14 int Finda(int o,int x) 15 { 16 return aset[o][x]==x?x:aset[o][x]=Finda(o,aset[o][x]); 17 } 18 void Merge(int a,int b,int k) 19 { 20 int f1=Finda(k,a),f2=Finda(k,b),len=1<<(k-1); 21 aset[k][f1]=f2; if(!k||f1==f2) return; 22 Merge(a,b,k-1),Merge(a+len,b+len,k-1); 23 } 24 int main() 25 { 26 scanf("%d%d",&n,&m),l1=log2(n); 27 for(int i=0;i<=l1;i++) 28 for(int j=1;j<=n;j++) 29 aset[i][j]=j; 30 for(int i=1;i<=m;i++) 31 { 32 scanf("%d%d%d%d",&t1,&t2,&t3,&t4); 33 if(t1>t3) swap(t1,t3),swap(t2,t4); 34 l2=log2(t2-t1+1),len=(1<<l2)-1; 35 Merge(t1,t3,l2),Merge(t2-len,t4-len,l2); 36 } 37 for(int i=1;i<=n;i++) 38 if(Finda(0,i)==i) ans++; 39 printf("%lld",9ll*Qpow(10,ans-1)%mod); 40 return 0; 41 }
SCOI 2016 美味
从高位向低位贪心，在主席树上二分找加上偏移量之后的区间里有没有值，有就贪心拿这一位
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=200005,inf=1e9,Maxx=(1<<18)-1; 6 int n,m,t1,t2,t3,t4,tot; 7 int dish[N],root[N],cnt[N*40],son[N*40][2]; 8 int Insert(int pre,int l,int r,int pos) 9 { 10 int nde=++tot; 11 son[nde][0]=son[pre][0]; 12 son[nde][1]=son[pre][1]; 13 cnt[nde]=cnt[pre]+1; 14 if(l!=r) 15 { 16 int mid=(l+r)>>1; 17 if(pos<=mid) 18 son[nde][0]=Insert(son[pre][0],l,mid,pos); 19 else 20 son[nde][1]=Insert(son[pre][1],mid+1,r,pos); 21 } 22 return nde; 23 } 24 int Query(int l,int r,int nl,int nr,int ll,int rr) 25 { 26 if(l>rr||r<ll) 27 return 0; 28 else if(l>=ll&&r<=rr) 29 return cnt[nr]-cnt[nl]; 30 else 31 { 32 int mid=(l+r)>>1; 33 int r1=Query(l,mid,son[nl][0],son[nr][0],ll,rr); 34 int r2=Query(mid+1,r,son[nl][1],son[nr][1],ll,rr); 35 return r1+r2; 36 } 37 } 38 int Ask(int l,int r,int ll,int rr,int k,int a,int b) 39 { 40 if(l==r) return a^l; 41 int mid=(l+r)>>1; 42 if(a&(1<<(k-1))) 43 { 44 int qry=Query(0,Maxx,ll,rr,max(l-b,0),max(mid-b,0)); 45 return qry?Ask(l,mid,ll,rr,k-1,a,b):Ask(mid+1,r,ll,rr,k-1,a,b); 46 } 47 else 48 { 49 int qry=Query(0,Maxx,ll,rr,max(mid+1-b,0),max(r-b,0)); 50 return qry?Ask(mid+1,r,ll,rr,k-1,a,b):Ask(l,mid,ll,rr,k-1,a,b); 51 } 52 } 53 int main() 54 { 55 scanf("%d%d",&n,&m); 56 for(int i=1;i<=n;i++) 57 { 58 scanf("%d",&dish[i]); 59 root[i]=Insert(root[i-1],0,Maxx,dish[i]); 60 } 61 while(m--) 62 { 63 scanf("%d%d%d%d",&t1,&t2,&t3,&t4); 64 printf("%d ",Ask(0,Maxx,root[t3-1],root[t4],18,t1,t2)); 65 } 66 return 0; 67 }