[关闭]
@SovietPower 2024-03-30T16:12:32.000000Z 字数 13290 阅读 45

New Temp

其它

线段树

beats

  1. /*
  2. 94908kb 47472ms
  3. 支持下面几种操作：
  4. 1.给一个区间[L,R] 加上一个数x 
  5. 2.把一个区间[L,R] 里小于x 的数变成x 
  6. 3.把一个区间[L,R] 里大于x 的数变成x 
  7. 4.求区间[L,R] 的和
  8. 5.求区间[L,R] 的最大值
  9. 6.求区间[L,R] 的最小值
  10. $Solution$
  11. 区间取max、min并维护区间和是普通线段树无法处理的。
  12. 对于操作二，维护区间最小值mn、最小值个数t、严格次小值se。
  13. 当mn>=x时，不需要改变，return；se>x>mn时，sum=sum+(x-mn)*t，打上区间max标记；
  14. 当x>=se>mn时，不会做，继续递归分别处理两个子区间，直到遇到前两种情况。
  15. 操作三同理，维护最大值、最大值个数、次大值。
  16. 复杂度$O(m\log^2n)$，常表现为$O(mlogn)$。
  17. 有两个修改(max,min)，太恶心了。。
  18. 比如：取min的时候不仅是改最大值，最小值也可能改（当然了。。然而这题就是忘了）。
  19. 最大值改了min标记也一定改（最大值是算了当前min标记后的）。
  20. 还有max标记也可能改，注意是取min而不是直接赋值（还有加法影响这个标记，原先的最大值并不一定是由这个标记得到的）。
  21. 还有min,max可能会使得区间变为同一个数(第一句话的情况)，这就需要特判然后把sum,次小值,次大值初始化掉。
  22. 还有如果mn没有跟mx一起变为v(上一种情况)，但是可能mn<v<=se，还要让次小值取个min。
  23. 还有常数太大。。考虑把min,max标记去掉，直接在父节点更新，并在适合的时候下传。-> 47s->40s.
  24. */
  25. struct Segment_Tree
  26. {
  27.     #define S N<<2
  28.     #define ls rt<<1
  29.     #define rs rt<<1|1
  30.     #define lson l,m,rt<<1
  31.     #define rson m+1,r,rt<<1|1
  32.     int mn[S],smn[S],tmn[S],mx[S],smx[S],tmx[S],sz[S],add[S],tagmn[S],tagmx[S];
  33.     LL sum[S];
  34.     #undef S
  35.     inline void Update(int rt)
  36.     {
  37.         int l=ls,r=rs; sum[rt]=sum[l]+sum[r];
  38.         if(mn[l]<mn[r]) mn[rt]=mn[l],smn[rt]=std::min(smn[l],mn[r]),tmn[rt]=tmn[l];
  39.         else if(mn[l]>mn[r]) mn[rt]=mn[r],smn[rt]=std::min(smn[r],mn[l]),tmn[rt]=tmn[r];
  40.         else mn[rt]=mn[l],smn[rt]=std::min(smn[l],smn[r]),tmn[rt]=tmn[l]+tmn[r];
  42.         if(mx[l]>mx[r]) mx[rt]=mx[l],smx[rt]=std::max(smx[l],mx[r]),tmx[rt]=tmx[l];
  43.         else if(mx[l]<mx[r]) mx[rt]=mx[r],smx[rt]=std::max(smx[r],mx[l]),tmx[rt]=tmx[r];
  44.         else mx[rt]=mx[l],smx[rt]=std::max(smx[l],smx[r]),tmx[rt]=tmx[l]+tmx[r];
  45.     }
  46.     inline void Add(int x,int v)
  47.     {
  48.         add[x]+=v, mn[x]+=v, mx[x]+=v, sum[x]+=1ll*v*sz[x];
  49.         if(smn[x]!=INF) smn[x]+=v;
  50.         if(smx[x]!=-INF) smx[x]+=v;
  51.         if(tagmn[x]!=INF) tagmn[x]+=v;
  52.         if(tagmx[x]!=-INF) tagmx[x]+=v;
  53.     }
  54.     inline void Min(int x,int v)
  55.     {
  56.         if(v<mx[x])
  57.         {
  58.             sum[x]-=1ll*tmx[x]*(mx[x]-v);
  59.             mx[x]=v, mn[x]=std::min(mn[x],v);//!
  60.             tagmn[x]=v/*! 首先要比最大值小才可能（且一定会）更新min标记*/,
  61.             tagmx[x]=std::min(tagmx[x],v);//!
  62.             if(mn[x]==mx[x]) sum[x]=1ll*sz[x]*v, tmn[x]=tmx[x]=sz[x], smn[x]=INF, smx[x]=-INF;//!
  63.             else smn[x]=std::min(smn[x],v);//!
  64.         }
  65.     }
  66.     inline void Max(int x,int v)
  67.     {
  68.         if(v>mn[x])
  69.         {
  70.             sum[x]+=1ll*tmn[x]*(v-mn[x]);
  71.             mn[x]=v, mx[x]=std::max(mx[x],v);
  72.             tagmx[x]=v, tagmn[x]=std::max(tagmn[x],v);
  73.             if(mn[x]==mx[x]) sum[x]=1ll*sz[x]*v, tmn[x]=tmx[x]=sz[x], smn[x]=INF, smx[x]=-INF;
  74.             else smx[x]=std::max(smx[x],v);
  75.         }
  76.     }
  77.     void PushDown(int rt)
  78.     {
  79.         if(add[rt]) Add(ls,add[rt]), Add(rs,add[rt]), add[rt]=0;
  80.         if(tagmn[rt]!=INF) Min(ls,tagmn[rt]), Min(rs,tagmn[rt]), tagmn[rt]=INF;
  81.         if(tagmx[rt]!=-INF) Max(ls,tagmx[rt]), Max(rs,tagmx[rt]), tagmx[rt]=-INF;
  82.     }
  83.     void Build(int l,int r,int rt)
  84.     {
  85.         sz[rt]=r-l+1, tagmn[rt]=INF, tagmx[rt]=-INF;
  86.         if(l==r)
  87.         {
  88.             tmn[rt]=tmx[rt]=1;
  89.             sum[rt]=mn[rt]=mx[rt]=read(), smn[rt]=INF, smx[rt]=-INF;
  90.             return;
  91.         }
  92.         Build(l,l+r>>1,ls), Build((l+r>>1)+1,r,rs);
  93.         Update(rt);
  94.     }
  95.     void Modify_Add(int l,int r,int rt,int L,int R,int v)
  96.     {
  97.         if(L<=l && r<=R) {Add(rt,v); return;}
  98.         PushDown(rt);
  99.         int m=l+r>>1;
  100.         if(L<=m) Modify_Add(lson,L,R,v);
  101.         if(m<R) Modify_Add(rson,L,R,v);
  102.         Update(rt);
  103.     }
  104.     void Modify_Max(int l,int r,int rt,int L,int R,int v)
  105.     {
  106.         if(mn[rt]>=v) return;
  107.         if(L<=l && r<=R && smn[rt]>v) {Max(rt,v); return;}
  108.         PushDown(rt);
  109.         int m=l+r>>1;
  110.         if(L<=m) Modify_Max(lson,L,R,v);
  111.         if(m<R) Modify_Max(rson,L,R,v);
  112.         Update(rt);
  113.     }
  114.     void Modify_Min(int l,int r,int rt,int L,int R,int v)
  115.     {
  116.         if(mx[rt]<=v) return;
  117.         if(L<=l && r<=R && smx[rt]<v) {Min(rt,v); return;}
  118.         PushDown(rt);
  119.         int m=l+r>>1;
  120.         if(L<=m) Modify_Min(lson,L,R,v);
  121.         if(m<R) Modify_Min(rson,L,R,v);
  122.         Update(rt);
  123.     }
  124.     int Query_Max(int l,int r,int rt,int L,int R)
  125.     {
  126.         if(L<=l && r<=R) return mx[rt];
  127.         PushDown(rt);
  128.         int m=l+r>>1;
  129.         if(L<=m)
  130.             if(m<R) return std::max(Query_Max(lson,L,R),Query_Max(rson,L,R));
  131.             else return Query_Max(lson,L,R);
  132.         else return Query_Max(rson,L,R);
  133.     }
  134.     int Query_Min(int l,int r,int rt,int L,int R)
  135.     {
  136.         if(L<=l && r<=R) return mn[rt];
  137.         PushDown(rt);
  138.         int m=l+r>>1;
  139.         if(L<=m)
  140.             if(m<R) return std::min(Query_Min(lson,L,R),Query_Min(rson,L,R));
  141.             else return Query_Min(lson,L,R);
  142.         else return Query_Min(rson,L,R);
  143.     }
  144.     LL Query_Sum(int l,int r,int rt,int L,int R)
  145.     {
  146.         if(L<=l && r<=R) return sum[rt];
  147.         PushDown(rt);
  148.         int m=l+r>>1;
  149.         if(L<=m)
  150.             if(m<R) return Query_Sum(lson,L,R)+Query_Sum(rson,L,R);
  151.             else return Query_Sum(lson,L,R);
  152.         else return Query_Sum(rson,L,R);
  153.     }
  154. }T;
  156. int main()
  157. {
  158.     #define S 1,n,1
  159.     int n=read(); T.Build(S);
  160.     for(int m=read(),opt,l,r; m--; )
  161.     {
  162.         opt=read(),l=read(),r=read();
  163.         if(opt==1) T.Modify_Add(S,l,r,read());
  164.         else if(opt==2) T.Modify_Max(S,l,r,read());
  165.         else if(opt==3) T.Modify_Min(S,l,r,read());
  166.         else if(opt==4) printf("%lld\n",T.Query_Sum(S,l,r));
  167.         else if(opt==5) printf("%d\n",T.Query_Max(S,l,r));
  168.         else printf("%d\n",T.Query_Min(S,l,r));
  169.     }
  170.     #undef S
  171.     return 0;
  172. }

mex

  1. /*
  2. 每次询问一个区间内最小没有出现过的自然数。
  3. 考虑[1,i]的mex[i]，显然是单调的 
  4. 而对于[l,r]与[l+1,r]，如果nxt[a[l]]>r，那么[l+1,r]中所有>a[l]的数显然要改成a[l] 
  5. 询问排序，离散化，预处理下nxt[]，剩下就是线段树的区间更新、查询了 
  6. 离散化的时候>=n的全部看做n就好了 
  7. 查询时是只需查r点的(l之前能更新r的已经更新完了，初始时是[1,r]，r点现在就是[l,r]了) 
  8. 单点即可不需要PushUp(也不好得某个区间的mex) 
  9. 非叶节点上的mex完全可以代替tag 
  10. 离散化需要注意 
  11. */
  12. #define now node[rt]
  13. #define lson node[node[rt].ls]
  14. #define rson node[node[rt].rs]
  15. const int N=2e5+5,INF=1e7;
  17. int n,m,A[N],mex[N]/*不要和A混用*/,tmp[N],nxt[N],las[N],ans[N];
  18. bool vis[N];
  19. struct Ques
  20. {
  21.     int l,r,id;
  22.     Ques() {}
  23.     Ques(int l,int r,int id): l(l),r(r),id(id) {}
  24.     bool operator <(const Ques &x)const {return l<x.l;}
  25. }q[N];
  26. struct Seg_Tree
  27. {
  28.     int tot;
  29.     struct Node
  30.     {
  31.         int ls,rs,mex;
  32.     }node[N<<1];
  33.     inline void Upd(int &x,int v) {x=std::min(x,v);}
  34.     inline void PushDown(int rt)
  35.     {
  36.         Upd(lson.mex,now.mex), Upd(rson.mex,now.mex);
  37.         now.mex=INF;
  38.     }
  39.     void Build(int l,int r)
  40.     {
  41.         int rt=tot++;
  42.         if(l==r) now.mex = mex[l];
  43.         else
  44.         {
  45.             int m=l+r>>1; now.mex=INF;
  46.             now.ls=tot, Build(l,m);
  47.             now.rs=tot, Build(m+1,r);
  48.         }
  49.     }
  50.     void Update(int l,int r,int rt,int L,int R,int v)
  51.     {
  52.         if(L<=l && r<=R) Upd(now.mex,v);
  53.         else
  54.         {
  55.             if(now.mex<INF) PushDown(rt);
  56.             int m=l+r>>1;
  57.             if(L<=m) Update(l,m,now.ls,L,R,v);
  58.             if(m<R) Update(m+1,r,now.rs,L,R,v);
  59.         }
  60.     }
  61.     int Query(int l,int r,int rt,int p)
  62.     {
  63.         if(l==r) return now.mex;
  64.         if(now.mex<INF) PushDown(rt);
  65.         int m=l+r>>1;
  66.         if(p<=m) return Query(l,m,now.ls,p);
  67.         else return Query(m+1,r,now.rs,p);
  68.     }
  69. }t;
  70. #undef now
  71. inline int read()
  72. {
  73.     int now=0,f=1;register char c=gc();
  74.     for(;!isdigit(c);c=gc()) if(c=='-') f=-1;
  75.     for(;isdigit(c);now=now*10+c-'0',c=gc());
  76.     return now*f;
  77. }
  78. int Find(int x,int r)
  79. {
  80.     int l=1,m;
  81.     while(l<r)
  82.     {
  83.         if(tmp[(m=l+r>>1)]<x) l=m+1;
  84.         else r=m;
  85.     }
  86.     return l;
  87. }
  89. int main()
  90. {
  91.     n=read(),m=read();
  92.     for(int i=1; i<=n; ++i) tmp[i]=A[i]=std::min(n,read());
  93.     std::sort(tmp+1,tmp+1+n);
  94.     int cnt=1;
  95.     for(int i=2; i<=n && !(tmp[i]==n&&tmp[i+1]==n); ++i)
  96.         if(tmp[i]!=tmp[i-1]) tmp[++cnt]=tmp[i];
  97.     for(int k=0,p,i=1; i<=n; ++i)
  98.     {
  99.         vis[p=Find(A[i],cnt)]=1;
  100.         if(A[i]==k)//只有在当前最小值出现时才更新。。mex...
  101.             while(vis[p])//p-1,vis[k]?
  102.             {
  103.                 ++k;
  104.                 if(tmp[++p]!=k) break;//离散化后 
  105.             }
  106.         mex[i]=k;
  107.     }
  108.     t.Build(1,n);
  109.     for(int i=0; i<=n; ++i) las[i]=n+1;
  110.     for(int tp,i=n; i; --i) nxt[i]=las[tp=Find(A[i],cnt)], las[tp]=i;//!
  111.     for(int l,i=1; i<=m; ++i) l=read(), q[i]=Ques(l,read(),i);
  112.     std::sort(q+1,q+1+m);
  113.     for(int now=1,i=1; i<=m; ++i)
  114.     {
  115.         while(now<q[i].l)
  116.             t.Update(1,n,0,now+1,nxt[now]-1,A[now]), ++now;
  117.         ans[q[i].id]=t.Query(1,n,0,q[i].r);
  118.     }
  119.     for(int i=1; i<=m; ++i) printf("%d\n",ans[i]);
  121.     return 0;
  122. }

区间加、乘

  1. int n,mod,Sum[N<<2],aTag[N<<2],mTag[N<<2];
  2. inline void PushUp(int rt)
  3. {
  4.     Sum[rt]=(Sum[rt<<1]+Sum[rt<<1|1])%mod;
  5. }
  6. inline void PushDown(int m,int rt)
  7. {
  8.     if(mTag[rt]!=1)
  9.     {
  10.         mTag[rt<<1]=1ll*mTag[rt<<1]*mTag[rt]%mod;
  11.         mTag[rt<<1|1]=1ll*mTag[rt<<1|1]*mTag[rt]%mod;
  12.         aTag[rt<<1]=1ll*aTag[rt<<1]*mTag[rt]%mod;
  13.         aTag[rt<<1|1]=1ll*aTag[rt<<1|1]*mTag[rt]%mod;
  14.         Sum[rt<<1]=1ll*Sum[rt<<1]*mTag[rt]%mod;
  15.         Sum[rt<<1|1]=1ll*Sum[rt<<1|1]*mTag[rt]%mod;
  16.         mTag[rt]=1;
  17.     }
  18.     if(aTag[rt])
  19.     {
  20.         aTag[rt<<1]+=aTag[rt], aTag[rt<<1]%=mod;
  21.         aTag[rt<<1|1]+=aTag[rt], aTag[rt<<1|1]%=mod;
  22.         Sum[rt<<1]=(1ll*Sum[rt<<1]+1ll*(m-(m>>1))*aTag[rt]%mod)%mod;
  23.         Sum[rt<<1|1]=(1ll*Sum[rt<<1|1]+1ll*(m>>1)*aTag[rt]%mod)%mod;
  24.         aTag[rt]=0;
  25.     }
  26. }
  27. void Build(int l,int r,int rt)
  28. {
  29.     mTag[rt]=1;
  30.     if(l==r)
  31.     {
  32.         Sum[rt]=read()%mod;
  33.         return;
  34.     }
  35.     int m=l+r>>1;
  36.     Build(l,m,rt<<1),Build(m+1,r,rt<<1|1);
  37.     PushUp(rt);
  38. }
  39. void Modify_Add(int l,int r,int rt,int L,int R,int v)
  40. {
  41.     if(L<=l && r<=R)
  42.     {
  43.         aTag[rt]+=v;
  44.         if(aTag[rt]>=mod) aTag[rt]-=mod;
  45.         Sum[rt]=(1ll*Sum[rt]+1ll*v*(r-l+1))%mod;
  46.         return;
  47.     }
  48.     PushDown(r-l+1,rt);
  49.     int m=l+r>>1;
  50.     if(L<=m) Modify_Add(l,m,rt<<1,L,R,v);
  51.     if(m<R) Modify_Add(m+1,r,rt<<1|1,L,R,v);
  52.     PushUp(rt);
  53. }
  54. void Modify_Mult(int l,int r,int rt,int L,int R,int v)
  55. {
  56.     if(L<=l && r<=R)
  57.     {
  58.         aTag[rt]=1ll*aTag[rt]*v%mod;
  59.         mTag[rt]=1ll*mTag[rt]*v%mod;
  60.         Sum[rt]=1ll*Sum[rt]*v%mod;
  61.         return;
  62.     }
  63.     PushDown(r-l+1,rt);
  64.     int m=l+r>>1;
  65.     if(L<=m) Modify_Mult(l,m,rt<<1,L,R,v);
  66.     if(m<R) Modify_Mult(m+1,r,rt<<1|1,L,R,v);
  67.     PushUp(rt);
  68. }
  69. int Query_Sum(int l,int r,int rt,int L,int R)
  70. {
  71.     if(L<=l && r<=R) return Sum[rt];
  72.     PushDown(r-l+1,rt);
  73.     int m=l+r>>1;long long res=0;
  74.     if(L<=m) res+=Query_Sum(l,m,rt<<1,L,R), res%=mod;
  75.     if(m<R) res+=Query_Sum(m+1,r,rt<<1|1,L,R), res%=mod;
  76.     return res;
  77. }

树链剖分

  1. #define MOD(x) x>=mod&&(x-=mod)
  2. #define ADD(x,v) (x+=v)>=mod&&(x-=mod)
  3. #define gc() getchar()
  4. #define MAXIN 200000
  5. //#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
  6. typedef long long LL;
  7. const int N=1e5+5;
  9. int n,mod,val[N],Enum,H[N],nxt[N<<1],to[N<<1],sz[N],son[N],top[N],fa[N],dep[N],dfn[N],ref[N];
  10. //char IN[MAXIN],*SS=IN,*TT=IN;
  11. struct Segment_Tree
  12. {
  13.     #define ls rt<<1
  14.     #define rs rt<<1|1
  15.     #define lson l,m,ls
  16.     #define rson m+1,r,rs
  17.     #define S N<<2
  18.     int t[S],tag[S];
  19.     #undef S
  21.     #define Add(rt,v,l) t[rt]+=1ll*(l)*v%mod, MOD(t[rt]), ADD(tag[rt],v)
  22.     #define Update(rt) t[rt]=t[ls]+t[rs], MOD(t[rt])
  23.     inline void PushDown(int rt,int m)
  24.     {
  25.         Add(ls,tag[rt],m-(m>>1)), Add(rs,tag[rt],(m>>1)), tag[rt]=0;
  26.     }
  27.     void Build(int l,int r,int rt)
  28.     {
  29.         if(l==r) {t[rt]=val[ref[l]]; return;}
  30.         int m=l+r>>1; Build(lson), Build(rson), Update(rt);
  31.     }
  32.     void Modify(int l,int r,int rt,int L,int R,int v)
  33.     {
  34.         if(L<=l && r<=R) {Add(rt,v,r-l+1); return;}
  35.         if(tag[rt]) PushDown(rt,r-l+1);
  36.         int m=l+r>>1;
  37.         if(L<=m) Modify(lson,L,R,v);
  38.         if(m<R) Modify(rson,L,R,v);
  39.         Update(rt);
  40.     }
  41.     int Query(int l,int r,int rt,int L,int R)
  42.     {
  43.         if(L<=l && r<=R) return t[rt];
  44.         if(tag[rt]) PushDown(rt,r-l+1);
  45.         int m=l+r>>1,res=0;
  46.         if(L<=m) res+=Query(lson,L,R);
  47.         if(m<R) res+=Query(rson,L,R);
  48.         return res>=mod?res-mod:res;
  49.     }
  50. }T;
  52. #define S 1,n,1
  53. inline int read()
  54. {
  55.     int now=0;register char c=gc();
  56.     for(;!isdigit(c);c=gc());
  57.     for(;isdigit(c);now=now*10+c-48,c=gc());
  58.     return now;
  59. }
  60. inline void AE(int u,int v)
  61. {
  62.     to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
  63.     to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
  64. }
  65. void DFS1(int x)
  66. {
  67.     int mx=0; sz[x]=1;
  68.     for(int i=H[x],v; i; i=nxt[i])
  69.         if((v=to[i])!=fa[x])
  70.             fa[v]=x, dep[v]=dep[x]+1, DFS1(v), sz[v]>mx&&(mx=sz[v],son[x]=v), sz[x]+=sz[v];
  71. }
  72. void DFS2(int x,int tp)
  73. {
  74.     static int Index=0;
  75.     top[x]=tp, ref[dfn[x]=++Index]=x;
  76.     if(son[x])
  77.     {
  78.         DFS2(son[x],tp);
  79.         for(int i=H[x],v; i; i=nxt[i])
  80.             if((v=to[i])!=fa[x] && v!=son[x]) DFS2(v,v);
  81.     }
  82. }
  83. int Query_LCA(int x,int y)
  84. {
  85.     while(top[x]!=top[y])
  86.     {
  87.         if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
  88.         x=fa[top[x]];
  89.     }
  90.     return dep[x]>dep[y]?y:x;
  91. }
  92. void ChainAdd(int w,int u,int v)
  93. {
  94.     while(top[u]!=top[v])
  95.     {
  96.         dep[top[u]]<dep[top[v]]&&(std::swap(u,v),0);
  97.         T.Modify(S,dfn[top[u]],dfn[u],w), u=fa[top[u]];
  98.     }
  99.     dep[u]>dep[v]&&(std::swap(u,v),0), T.Modify(S,dfn[u],dfn[v],w);
  100. }
  101. int Query(int u,int v)
  102. {
  103.     LL res=0;
  104.     while(top[u]!=top[v])
  105.     {
  106.         dep[top[u]]<dep[top[v]]&&(std::swap(u,v),0);
  107.         res+=T.Query(S,dfn[top[u]],dfn[u]), u=fa[top[u]];
  108.     }
  109.     dep[u]>dep[v]&&(std::swap(u,v),0);
  110.     return (res+T.Query(S,dfn[u],dfn[v]))%mod;
  111. }
  113. int main()
  114. {
  115.     int n=read(),m=read(),root=read(); ::n=n, mod=read();
  116.     for(int i=1; i<=n; ++i) val[i]=read();
  117.     for(int i=1; i<n; ++i) AE(read(),read());
  118.     DFS1(root), DFS2(root,root), T.Build(S);
  119.     for(int x; m--; )
  120.     {
  121.         switch(read())
  122.         {
  123.             case 1: ChainAdd(read(),read(),read()); break;
  124.             case 2: printf("%d\n",Query(read(),read())); break;
  125.             case 3: x=read(), T.Modify(S,dfn[x],dfn[x]+sz[x]-1,read()); break;
  126.             case 4: x=read(), printf("%d\n",T.Query(S,dfn[x],dfn[x]+sz[x]-1)); break;
  127.         }
  128.     }
  129.     return 0;
  130. }

树状数组

  1. struct BIT
  2. {
  3.     int n,t[N*4];//2n!
  4.     #define lb(x) (x&-x)
  5.     inline void Add(int p)
  6.     {
  7.         for(; p<=n; p+=lb(p)) ++t[p];
  8.     }
  9.     inline void Delete(int p)
  10.     {
  11.         for(; p<=n; p+=lb(p)) --t[p];
  12.     }
  13.     inline int Query(int p)
  14.     {
  15.         int res=0;
  16.         for(; p; p^=lb(p)) res+=t[p];
  17.         return res;
  18.     }
  19.     void Init(int nn) {
  20.         //...
  21.     }
  22.     inline int Kth(int k)
  23.     {
  24.         int l=1,r=n,mid;
  25.         while(l<r)
  26.             if(Query(mid=l+r>>1)<k) l=mid+1;
  27.             else r=mid;
  28.         return l;
  29.     }
  30. }T;

并查集

  1. int Getfa(int x) {
  2.     return x==fa[x]?x:fa[x]=Getfa(fa[x]);
  3. }
  4. if((r1=Getfa(x))!=(r2=Getfa(y)))
  5. {
  6.     fa[r2]=r1;      tag[r1]|=tag[r2];
  7.     if(mx[r2]>mx[r1]) smx[r1]=std::max(mx[r1],smx[r2]), mx[r1]=mx[r2];
  8.     else smx[r1]=std::max(smx[r1],mx[r2]);
  9. }

KMP

  1. int fail[N];
  2. char s[N],p[N];
  4. void Get_Fail()
  5. {
  6.     fail[0]=fail[1]=0;
  7.     int l=strlen(s+1);
  8.     for(int j=0,i=2; i<=l; ++i)
  9.     {
  10.         while(j && s[i]!=s[j+1]) j=fail[j];
  11.         fail[i]= s[i]==s[j+1]?++j:0;
  12.     }
  13. }
  14. void KMP()
  15. {
  16.     int l=strlen(p+1),ls=strlen(s+1);
  17.     for(int i=1,j=0; i<=l; ++i)
  18.     {
  19.         while(j && p[i]!=s[j+1]) j=fail[j];
  20.         if(p[i]==s[j+1]) ++j;
  21.         if(j==ls) printf("%d\n",i-ls+1);
  22.     }
  23.     for(int i=1; i<=ls; ++i)
  24.         printf("%d ",fail[i]);
  25. }
  26. scanf("%s%s",p+1,s+1);
  27. Get_Fail();
  28. KMP();

Dijkstra

  1. inline void AE(int u,int v,int w)
  2. {
  3.     to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
  4.     to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
  5. }
  6. void Dijkstra(int s,int t,int n)
  7. {
  8.     static int dis[N];
  9.     static bool vis[N];
  10.     static std::priority_queue<pr> q;
  12.     memset(dis,0x3f,sizeof dis);
  13.     dis[s]=dis[s+n]=0, q.push(mp(0,s));
  14.     while(!q.empty())
  15.     {
  16.         int x=q.top().second; q.pop();
  17.         if(vis[x]) continue;
  18.         vis[x]=1;
  19.         for(int i=H[x],v; i; i=nxt[i])
  20.             if(dis[v=to[i]]>dis[x]+len[i])
  21.                 q.push(mp(-(dis[v]=dis[x]+len[i]),v));
  22.     }
  23.     printf("%d\n",dis[t]);
  24. }

差分约束

考虑最短路中的松弛操作：if(dis[v]>dis[x]+w) dis[v]=dis[x]+w，也就是强制使得满足。
所以对于的限制，可以连一条边。这样求的最大值，就是求的最短路。
如果限制是，同理连边。的最小值就是求的最长路。
如果两种限制都有，就把变成。
解的存在性：
比如求的最大值：若图中存在负环，则的最短路无穷小，则不存在最大值（无解）。
若和就不在同一连通块，则的最短路无穷大，最大值无穷大（或者存在无数多解）。
否则有解。
可以根据入队次数判负环，也可以据此判正环。虽然效率都不高就是了。不能求最长路（本质是贪心）。
如何判断解唯一：
对原图求一遍最短路。将原图取反，边权取反，求一遍最长路。
一个标号对应的是能取到的最小值，一个是最大值。如果相同则解唯一。

  1. /*
  2. 差分约束：对于 n[a] - n[b] <= w 的不等式，可以转化成 n[a] <= n[b] + w
  3. 换个形式 dis[a] <= dis[b] + w(a,b)
  4. 用SPFA做，dis[a]>dis[b]+w(a,b) 时会进行松弛 
  5. 求最小值用最长路，求最大值用最短路 
  6. 1.>= 求最小值。为什么是最长路？如果是最短路，很多条件可能不被满足， 
  7. (SPFA松弛时是将 dis[a]>dis[b]+w(a,b) -> dis[a]=dis[b]+w(a,b))
  8. 2.<= 求最大值。为什么是最短路？因为要满足所有小于等于的条件，只有最短的路才能满足图中所有约束条件；如果比最短路长，可能有些条件不被满足 
  9. 3.如果出现没有等号的项，用整数的连续性 
  10. */
  11. bool SPFA()
  12. {
  13.     for(int i=1; i<=T; ++i) dis[i]=-INF,tm[i]=0;
  14.     tm[0]=dis[0]=0, q.push(0);
  15.     while(!q.empty())
  16.     {
  17.         int x=q.front();q.pop();
  18.         inq[x]=0;
  19.         for(int i=H[x]; i; i=nxt[i])
  20.             if(dis[to[i]]<dis[x]+val[i])
  21.             {
  22.                 dis[to[i]]=dis[x]+val[i];
  23.                 if(!inq[to[i]])
  24.                 {
  25.                     if(++tm[to[i]]>T) return 0;
  26.                     inq[to[i]]=1,q.push(to[i]);
  27.                 }
  28.             }
  29.     }
  30.     return 1;
  31. }
  32. bool Check(int x)
  33. {
  34.     Enum=0, memset(H,0,sizeof H);
  35.     for(int i=1; i<8; ++i) AddEdge(16+i,i,R[i]-x);
  36.     for(int i=8; i<=T; ++i) AddEdge(i-8,i,R[i]);
  37.     for(int i=1; i<=T; ++i) AddEdge(i,i-1,-B[i]),AddEdge(i-1,i,0);
  38.     AddEdge(0,T,x), AddEdge(T,0,-x);
  39.     return SPFA();
  40. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注