[关闭]
@Cyani 2019-03-23T01:17:43.000000Z 字数 34750 阅读 825

OI review

多项式

神仙NTT模板

利用了ull能承受18次10^18级别的数相加的性质。理论上支持最多只有 。否则需要及时取模

  1. #void dft(poly &A,int n){
  2.     static ll W[N<<1],*H[30],*las=W,mx=0;
  3.     for(;mx<n;mx++){
  4.         H[mx]=las;ll w=1,wn=power(g,(mod-1)>>(mx+1));
  5.         REP(i,1<<mx)*las++=w,w=w*wn%mod;
  6.     }
  7.     static ll a[N];A.resize(1<<n);
  8.     for(int i=0,j=0;i<(1<<n);++i){
  9.         a[i]=A[j];
  10.         for(int k=1<<(n-1);(j^=k)<k;k>>=1);
  11.     }
  12.     for(int k=0,d=1;k<n;k++,d<<=1)
  13.         for(int i=0;i<(1<<n);i+=d<<1){
  14.             ll *l=a+i,*r=a+i+d,*w=H[k],t;
  15.             for(int j=0;j<d;++j,++l,++r){
  16.                 t=(*w++)*(*r)%mod;//t=(*w++)*(*r%mod)%mod;
  17.                 *r=*l+mod-t,*l+=t;
  18.             }
  19.         }
  20.     REP(i,1<<n)A[i]=a[i]%mod;
  21. }

完整模板

注意🐮迭之前之后都需要resize

  1. const int mod=998244353;
  2. namespace Poly{
  3.     const int N=(1<<20)+5,g=3;
  4.     inline int power(int x,int p){
  5.         int res=1;
  6.         for(;p;p>>=1,x=(ll)x*x%mod)
  7.             if(p&1)res=(ll)res*x%mod;
  8.         return res;
  9.     }
  10.     inline int fix(const int x){
  11.         return x>=mod?x-mod:x;
  12.     }
  13.     void dft(poly &A,int n){
  14.         static ull W[N<<1],*H[30],*las=W,mx=0;
  15.         for(;mx<n;mx++){
  16.             H[mx]=las;ull w=1,wn=power(g,(mod-1)>>(mx+1));
  17.             REP(i,1<<n)*las++=w,w=w*wn%mod;
  18.         }
  19.         if(A.size()!=(1<<n))A.resize(1<<n);
  20.         static ull a[N];
  21.         for(int i=0,j=0;i<(1<<n);++i){
  22.             a[i]=A[j];
  23.             for(int k=1<<(n-1);(j^=k)<k;k>>=1);
  24.         }
  25.         for(int k=0,d=1;k<n;k++,d<<=1)
  26.             for(int i=0;i<(1<<n);i+=(d<<1)){
  27.                 ull *l=a+i,*r=a+i+d,*w=H[k],t;
  28.                 for(int j=0;j<d;j++,l++,r++){
  29.                     t=(*r)*(*w++)%mod;
  30.                     *r=*l+mod-t,*l+=t;
  31.                 }
  32.             }
  33.         REP(i,1<<n)A[i]=a[i]%mod;
  34.     }
  35.     void idft(poly &a,int n){
  36.         a.resize(1<<n),reverse(a.begin()+1,a.end());
  37.         dft(a,n);int inv=power(1<<n,mod-2);
  38.         REP(i,1<<n)a[i]=(ll)a[i]*inv%mod;
  39.     }
  40.     poly FIX(poly a){
  41.         while(!a.empty()&&!a.back())a.pop_back();
  42.         return a;
  43.     }
  44.     poly add(poly a,poly b,int op=0){
  45.         a.resize(max(a.size(),b.size()));
  46.         REP(i,b.size())a[i]=fix(op?a[i]+mod-b[i]:a[i]+b[i]);
  47.         return FIX(a);
  48.     }
  49.     poly mul(poly a,poly b,int t=1){
  50.         if(t==1&&a.size()+b.size()<=24){
  51.             poly c(a.size()+b.size(),0);
  52.             REP(i,a.size())REP(j,b.size())
  53.                 c[i+j]=(c[i+j]+(ll)a[i]*b[j])%mod;
  54.             return FIX(c);
  55.         }
  56.         int n=1,aim=a.size()*t+b.size();
  57.         while((1<<n)<=aim)n++;
  58.         dft(a,n),dft(b,n);
  59.         if(t==1)REP(i,1<<n)a[i]=(ll)a[i]*b[i]%mod;
  60.         else REP(i,1<<n)a[i]=(ll)a[i]*a[i]%mod*b[i]%mod;
  61.         idft(a,n),a.resize(aim);
  62.         return FIX(a);
  63.     }
  64.     poly mul(poly a,int b){
  65.         REP(i,a.size())a[i]=(ll)a[i]*b%mod;
  66.         return FIX(a);
  67.     }
  69.     poly inv(poly a,int n){     //a[0] != 0
  70.         a.resize(n);poly b;
  71.         if(n==1){
  72.             b.pb(power(a[0],mod-2));
  73.             return b;
  74.         }
  75.         b=inv(a,n+1>>1);
  76.         b=add(mul(b,2),mul(b,a,2),1);
  77.         return b.resize(n),b;
  78.     }
  80.     poly Der(poly a){
  81.         REP(i,a.size()-1)a[i]=(ll)(i+1)*a[i+1]%mod;
  82.         return a.pop_back(),a;
  83.     }
  84.     poly Int(poly a){
  85.         static int inv[N];inv[1]=1;a.pb(0);
  86.         rep(i,2,a.size())inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
  87.         per(i,a.size()-1,1)a[i]=(ll)a[i-1]*inv[i]%mod;
  88.         return a[0]=0,a;
  89.     }
  90.     poly Ln(poly a,int n){      //a[0] = 1
  91.         a=mul(Der(a),inv(a,n)),a.resize(n-1);
  92.         return FIX(Int(a));
  93.     }
  94.     poly Exp(poly a,int n){     //a[0] = 0
  95.         a.resize(n);poly b,one(1,1);
  96.         if(n==1)return one;
  97.         b=Exp(a,n+1>>1);
  98.         b=mul(b,add(add(a,Ln(b,n),1),one));
  99.         return b.resize(n),b;
  100.     }
  102.     poly Div(poly a,poly b){
  103.         poly c;int n=a.size()-1,m=b.size()-1;
  104.         if(n<m)return c;
  105.         reverse(a.begin(),a.end());a.resize(n-m+1);
  106.         reverse(b.begin(),b.end());b.resize(n-m+1);
  107.         c=mul(a,inv(b,n-m+1));c.resize(n-m+1);
  108.         return reverse(c.begin(),c.end()),c;
  109.     }
  110.     poly Mod(poly a,poly b){
  111.         return FIX(add(a,mul(Div(a,b),b),1));
  112.     }
  114.     inline int chk(int x){
  115.         return power(x,(mod-1)/2)==1;
  116.     }
  117.     inline int R(){return rand()%mod;}
  118.     inline pii mul(pii a,pii b,int w){
  119.         return mp(((ll)a.fi*b.fi+(ll)a.se*b.se%mod*w)%mod,
  120.                   ((ll)a.fi*b.se+(ll)a.se*b.fi)%mod);
  121.     }
  122.     inline int Sqrt(int x){
  123.         if(!chk(x))return -1;
  124.         int a=R();while(chk(((ll)a*a-x+mod)%mod))a=R();
  125.         int w=((ll)a*a-x+mod)%mod,p=(mod+1)/2;
  126.         pii res=mp(1,0),t=mp(a,1);
  127.         for(;p;p>>=1,t=mul(t,t,w))
  128.             if(p&1)res=mul(res,t,w);
  129.         assert(!res.se);
  130.         return min(res.fi,mod-res.fi);
  131.     }
  132.     poly Sqrt(poly a,int n){
  133.         if(n==1){
  134.             poly b(1,Sqrt(a[0]));
  135.             return b;
  136.         }
  137.         a.resize(n);poly b=Sqrt(a,n+1>>1);
  138.         b=mul(add(b,mul(a,inv(b,n))),(mod+1)/2);
  139.         return b.resize(n),b;
  140.     }
  142.     poly fastpow(poly a,ll k,int n) {
  143.         a.resize(n),a=FIX(a);
  144.         if(!a.size())return a;
  145.         int st=0,base=0;while(!a[st])++st;
  146.         if(st*k>=n)return a.resize(0),a;
  147.         REP(i,a.size()-st)a[i]=a[i+st];
  148.         if(st)a.resize(a.size()-st);
  149.         base=a[0];ll inv=power(base,mod-2);
  150.         REP(i,a.size())a[i]=a[i]*inv%mod;
  151.         a=FIX(Exp(mul(Ln(a, n),k%mod),n));;
  152.         if(st){
  153.             reverse(a.begin(),a.end());
  154.             a.resize(a.size()+st*k);
  155.             reverse(a.begin(),a.end());
  156.             a.resize(n),a=FIX(a);
  157.         }
  158.         base=power(base,k);
  159.         REP(i,a.size())a[i]=(ll)a[i]*base%mod;
  160.         return FIX(a);
  161.     }
  163.     #define lc (o<<1)
  164.     #define rc (o<<1|1)
  165.     #define mid ((l+r)>>1)
  166.     poly owo[N<<1];
  167.     void Qinit(int o,int l,int r,vi &x){
  168.         if(l==r){
  169.             owo[o].resize(2);
  170.             owo[o][1]=1,owo[o][0]=mod-x[l];
  171.             return;
  172.         }
  173.         Qinit(lc,l,mid,x),Qinit(rc,mid+1,r,x);
  174.         if(o>=2)owo[o]=mul(owo[lc],owo[rc]);
  175.     }
  176.     void Q(int o,int l,int r,poly f,vi &y){
  177.         if(l==r){y[l]=(f.empty()?0:f[0]);return;}
  178.         Q(lc,l,mid,Mod(f,owo[lc]),y);
  179.         Q(rc,mid+1,r,Mod(f,owo[rc]),y);
  180.     }
  181.     void Q(int n,int m,poly f,vi &x,vi &y){     //初始化大小！
  182.         Qinit(1,0,m-1,x),Q(1,0,m-1,f,y);
  183.     }
  184.     poly ovo[N<<1];
  185.     void Cinit(int o,int l,int r,vi &x){
  186.         if(l==r){
  187.             ovo[o].resize(2);
  188.             ovo[o][1]=1,ovo[o][0]=mod-x[l];
  189.             return;
  190.         }
  191.         Cinit(lc,l,mid,x),Cinit(rc,mid+1,r,x);
  192.         ovo[o]=mul(ovo[lc],ovo[rc]);
  193.     }
  194.     poly C(int o,int l,int r,vi &z){
  195.         if(l==r){
  196.             poly res(1,z[l]);
  197.             return res;
  198.         }
  199.         return add(mul(C(lc,l,mid,z),ovo[rc]),
  200.                    mul(C(rc,mid+1,r,z),ovo[lc]));
  201.     }
  202.     poly C(int n,vi &x,vi &y){                  //初始化大小！
  203.         Cinit(1,0,n-1,x);
  204.         poly M=Der(ovo[1]),z(n,0);
  205.         Q(n,n,M,x,z);
  206.         REP(i,n)z[i]=(ll)y[i]*power(z[i],mod-2)%mod;
  207.         poly res=C(1,0,n-1,z);
  208.         return res.resize(n),res;
  209.     }
  210.     #undef lc
  211.     #undef rc
  212.     #undef mid
  213. }
  214. using namespace Poly;

拆系数FFT

玄学方法可以优化到4次dft，不过似乎只快了20%

  1. const int mod=1000000007;
  2. const int N=200005,M=(1<<15);
  3. const ld PI=acos(-1);
  4. struct C{
  5.     ld r,i;
  6.     inline friend C operator + (const C &a,const C &b){
  7.         return (C){a.r+b.r,a.i+b.i};
  8.     }
  9.     inline friend C operator - (const C &a,const C &b){
  10.         return (C){a.r-b.r,a.i-b.i};
  11.     }
  12.     inline friend C operator * (const C &a,const C &b){
  13.         return (C){a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r};
  14.     }
  15.     inline friend C operator / (const C &a,const ld &b){
  16.         return (C){a.r/b,a.i/b};
  17.     }
  18.     inline C rev(){
  19.         return (C){r,-i};
  20.     }
  21. };
  22. const C owo1=(C){0.5,0},owo2=(C){0,-0.5},I=(C){0,1};
  23. namespace Poly{
  24.     const int N=(1<<19)+5;
  25.     poly naive_mul(const poly &A,const poly &B){
  26.         poly C(A.size()+B.size()-1,0);
  27.         REP(i,A.size())REP(j,B.size())
  28.             C[i+j]=(C[i+j]+(ll)A[i]*B[j])%mod;
  29.         return C;
  30.     }
  31.     void dft(C *a,int n){
  32.         static C W[N<<1],*H[30],*las=W;
  33.         static int R[N],mx=0;
  34.         for(;mx<n;++mx){
  35.             H[mx]=las;int m=(1<<(mx+1));
  36.             REP(i,1<<mx)*las++=(C){cos(2*PI*i/m),sin(2*PI*i/m)};
  37.         }
  38.         REP(i,1<<n){
  39.             R[i]=(i&1?R[i^1]|1<<(n-1):R[i>>1]>>1);
  40.             if(i<R[i])swap(a[i],a[R[i]]);
  41.         }
  42.         for(int k=0,d=1;k<n;++k,d<<=1)
  43.             for(int i=0;i<(1<<n);i+=(d<<1)){
  44.                 C *l=a+i,*r=a+i+d,*w=H[k],x,y;
  45.                 for(int j=0;j<d;++j,++l,++r){
  46.                     x=*l,y=(*r)*(*w++);
  47.                     *l=x+y,*r=x-y;
  48.                 }
  49.             }
  50.     }
  51.     void idft(C *a,int n){
  52.         //reverse(a+1,a+(1<<n));
  53.         dft(a,n);int m=1<<n;
  54.         REP(i,m)a[i]=a[i]/m;
  55.     }
  56.     poly mul(const poly &A,const poly &B){
  57.         int aim=(A.size()+B.size()-1),n=1;
  58.         if(aim<=32)return naive_mul(A,B);
  59.         while((1<<n)<=aim)++n;
  60.         C *a=new C[1<<n],*b=new C[1<<n];
  61.         C *c=new C[1<<n],*d=new C[1<<n];
  62.         REP(i,1<<n){
  63.             if(i<A.size())a[i]=(C){ld(A[i]>>15),ld(A[i]&(M-1))};
  64.             else a[i]=(C){0,0};
  65.             if(i<B.size())b[i]=(C){ld(B[i]>>15),ld(B[i]&(M-1))};
  66.             else b[i]=(C){0,0};
  67.         }
  68.         dft(a,n),dft(b,n);
  69.         REP(i,1<<n)c[i]=a[i],d[i]=b[i];
  70.         REP(i,1<<n){
  71.             int j=(!i?0:(1<<n)-i);
  72.             static C a1,a2,b1,b2;
  73.             a1=owo1*(c[i]+c[j].rev());
  74.             a2=owo2*(c[i]-c[j].rev());
  75.             b1=owo1*(d[i]+d[j].rev());
  76.             b2=owo2*(d[i]-d[j].rev());
  77.             a[j]=a1*b1+I*a1*b2;
  78.             b[j]=a2*b1+I*a2*b2;
  79.         }
  80.         idft(a,n),idft(b,n);
  81.         poly C(aim,0);
  82.         REP(i,aim){
  83.             int a1=(ll)(a[i].r+0.5)%mod;
  84.             int a2=(ll)(a[i].i+0.5)%mod;
  85.             int b1=(ll)(b[i].r+0.5)%mod;
  86.             int b2=(ll)(b[i].i+0.5)%mod;
  87.             C[i]=(((ll)a1<<30)+((ll)a2<<15)+((ll)b1<<15)+b2)%mod;
  88.         }
  89.         delete [] a;
  90.         delete [] b;
  91.         delete [] c;
  92.         delete [] d;
  93.         return C;
  94.     }
  95. }

数据结构

LCT

维护子树信息。注意虚实边切换对答案的影响

共价大爷游长沙

  1. const int N=500005;
  2. int t[N][2],fa[N],rev[N];
  3. ui s[N],w[N],is[N];
  5. inline int isr(int x){
  6.     return t[fa[x]][0]!=x&&t[fa[x]][1]!=x;
  7. }
  8. inline void up(int x){
  9.     s[x]=s[t[x][0]]^s[t[x][1]]^is[x]^w[x];
  10. }
  11. inline void Rev(int x){
  12.     if(!x)return;swap(t[x][0],t[x][1]),rev[x]^=1;
  13. }
  14. inline void down(int x){
  15.     if(rev[x])Rev(t[x][0]),Rev(t[x][1]),rev[x]=0;
  16. }
  17. #define B(x) (t[fa[x]][1]==x)
  18. inline void rot(int x){
  19.     int y=fa[x],z=fa[y],f=B(x);
  20.     fa[t[y][f]=t[x][f^1]]=y;
  21.     if(!isr(y))t[z][B(y)]=x;fa[x]=z;
  22.     fa[t[x][f^1]=y]=x,up(y),up(x);
  23. }
  24. inline void push(int x){
  25.     if(!isr(x))push(fa[x]);down(x);
  26. }
  27. inline void spl(int x){
  28.     push(x);
  29.     for (;!isr(x);rot(x)){
  30.         if(!isr(fa[x]))rot(B(x)^B(fa[x])?x:fa[x]);
  31.     }
  32. }
  33. inline void access(int x){
  34.     int y=0;
  35.     while(x){
  36.         spl(x),is[x]^=s[t[x][1]],is[x]^=s[t[x][1]=y],up(x);
  37.         y=x,x=fa[x];
  38.     }
  39. }
  40. inline void evert(int x){
  41.     access(x),spl(x),Rev(x);
  42. }
  43. inline void cut(int x,int y){
  44.     evert(x),access(y),spl(y);
  45.     t[y][0]=fa[x]=0,up(y);
  46. }
  47. inline void link(int x,int y){
  48.     evert(x),access(y),spl(y);
  49.     fa[x]=y,is[y]^=s[x],up(y);
  50. }
  51. inline void upd(int x,ui y){
  52.     access(x),spl(x),w[x]^=y,up(x);
  53. }
  54. inline ui qry(int x,int y){
  55.     return evert(x),access(y),spl(y),s[x];
  56. }

平衡树

维护凸包（最好离线CDQ解决..）注意维护点的偏序关系。

  1. namespace Cov {
  2. /*
  3. 实现接口：
  4. init， 初始化
  5. insert(point p)， 插入点p，并动态维护上凸包
  6. query(point p)， 询问凸包上与其点积最大的点
  7. */
  8.     const int N = 250005;
  9.     int lc[N], rc[N], sz[N], fix[N];
  10.     int pre[N], suf[N];
  11.     point key[N];
  12.     int tot, rt;
  14.     inline int nw(point p) {
  15.         int o = ++ tot;
  16.         key[o] = p, fix[o] = rand(),
  17.         lc[o] = rc[o] = pre[o] = suf[o] = 0, sz[o] = 1;
  18.         return o;
  19.     }
  20.     inline void up(int o) {
  21.         sz[o] = sz[lc[o]] + sz[rc[o]] + 1;
  22.     }
  23.     int make(int x, int y) {
  24.         if (!x || !y) return x | y;
  25.         return fix[x] > fix[y]
  26.         ? (rc[x] = make(rc[x], y), up(x), x)
  27.         : (lc[y] = make(x, lc[y]), up(y), y);
  28.     }
  29.     pii split(int x, point k) {
  30.         if (!x) return make_pair(0, 0);
  31.         pii y; key[x] <= k
  32.         ? (y = split(rc[x], k), rc[x] = y.fi, y.fi = x)
  33.         : (y = split(lc[x], k), lc[x] = y.se, y.se = x);
  34.         return up(x), y;
  35.     }
  36.     inline int kth(int x, int k) {
  37.         if (!x) return 0;
  38.         for (;;) {
  39.             int lsz = sz[lc[x]] + 1;
  40.             if (lsz == k) return x;
  41.             if (lsz > k) x = lc[x];
  42.             else k -= lsz, x = rc[x];
  43.         }
  44.     }
  46.     point getL(int u, point p) {
  47.         if (!u) return point(-inf, -inf);
  48.         if (!pre[u] || cross(key[pre[u]], key[u], p) < 0)
  49.             return max(key[u], getL(rc[u], p));
  50.         return getL(lc[u], p);
  51.     }
  52.     point getR(int u, point p) {
  53.         if (!u) return point(inf, inf);
  54.         if (!suf[u] || cross(key[suf[u]], key[u], p) > 0)
  55.             return min(key[u], getR(lc[u], p));
  56.         return getR(rc[u], p);
  57.     }
  59.     inline void init() {
  60.         tot = rt = 0;
  61.     }
  62.     inline void insert(point p) {
  63.         pii x = split(rt, p);
  64.         int a = kth(x.fi, sz[x.fi]), b = suf[a];
  65.         if (a && b && cross(key[a], p, key[b]) >= 0||a&&key[a]==p) {
  66.             rt = make(x.fi, x.se);
  67.             return;
  68.         }
  69.         point L = getL(x.fi, p), R = getR(x.se, p);
  70.         pii y = split(x.fi, L), z = split(x.se, point(R.x, R.y - 1));
  71.         a = kth(y.fi, sz[y.fi]), b = kth(z.se, 1);
  72.         int o = nw(p);
  73.         pre[o] = a, suf[o] = b;
  74.         if (a) suf[a] = o;
  75.         if (b) pre[b] = o;
  76.         rt = make(y.fi, make(o, z.se));
  77.     }
  78.     ll dfs(int u, point p) {
  79.         ll res = dot(p, key[u]);
  80.         if (rc[u] && dot(p, key[suf[u]]) >= res) return dfs(rc[u], p);
  81.         if (lc[u] && dot(p, key[pre[u]]) >= res) return dfs(lc[u], p);
  82.         return res;
  83.     }
  84.     inline ll query(point p) {
  85.         return rt ? dfs(rt, p) : 0;
  86.     }
  87. }

可持久化

只需要类似主席树那样拷贝即可。

  1. namespace treap{
  2.     int lc[N],rc[N],sz[N],key[N],val[N];
  3.     int size=0;
  4.     inline int nw(int x){
  5.         int o=++size;
  6.         key[o]=rand();
  7.         val[o]=x;
  8.         sz[o]=1;
  9.         return o;
  10.     }
  11.     inline int copy(int x){
  12.         int o=nw(val[x]);
  13.         key[o]=key[x];
  14.         sz[o]=sz[x];
  15.         lc[o]=lc[x];
  16.         rc[o]=rc[x];
  17.         return o;
  18.     }
  19.     inline void up(int o){
  20.         sz[o]=sz[lc[o]]+1+sz[rc[o]];
  21.     }
  22.     inline int merge(int x,int y){
  23.         if(!x||!y)return x|y;
  24.         if(key[x]<key[y]){
  25.             int o=copy(x);
  26.             rc[o]=merge(rc[o],y);
  27.             return up(o),o;
  28.         }
  29.         else{
  30.             int o=copy(y);
  31.             lc[o]=merge(x,lc[o]);
  32.             return up(o),o;
  33.         }
  34.     }
  35.     inline pii split(int o,int k){
  36.         if(!o)return mp(0,0);
  37.         if(k==0)return mp(0,o);
  38.         if(k==sz[o])return mp(o,0);
  39.         if(k<=sz[lc[o]]){
  40.             int u=copy(o);
  41.             pii y=split(lc[u],k);
  42.             lc[u]=y.se;
  43.             return up(u),mp(y.fi,u);
  44.         }
  45.         else{
  46.             int u=copy(o);
  47.             pii y=split(rc[u],k-1-sz[lc[u]]);
  48.             rc[u]=y.fi;
  49.             return up(u),mp(u,y.se);
  50.         }
  51.     }
  52.     inline int ins(int o,int k,int x){
  53.         pii y=split(o,k-1);
  54.         return merge(y.fi,merge(nw(x),y.se));
  55.     }
  56.     inline int del(int o,int k){
  57.         pii y=split(o,k-1);
  58.         pii z=split(y.se,1);
  59.         return merge(y.fi,z.se);
  60.     }
  61.     inline int qry(int o,int k){
  62.         for(;;){
  63.             if(k==sz[lc[o]]+1)return val[o];
  64.             if(k<=sz[lc[o]])o=lc[o];
  65.             else k-=1+sz[lc[o]],o=rc[o];
  66.         }
  67.     }
  68. }

线段树嵌套treap

注意treap的懒标记是全局的，所以也需要在线段树上放

  1. const int N=250000*50;
  2. namespace treap{
  3.     struct node{
  4.         int lc,rc,key,sz,tag,val,best,lzy;
  5.     }T[N];
  6.     int stk[N],siz,top;
  7.     inline int nw(int p,int owo){
  8.         int o;
  9.         if(top)o=stk[top--];
  10.         else o=++siz;
  11.         T[o].lc=T[o].rc=T[o].lzy=0;
  12.         T[o].key=rand();
  13.         T[o].sz=1;
  14.         T[o].tag=p;
  15.         T[o].val=owo;
  16.         T[o].best=owo;
  17.         return o;
  18.     }
  19.     inline void push(int o){
  20.         stk[++top]=o;
  21.     }
  22.     inline void plus(int o,int x){
  23.         if(o)T[o].tag+=x,T[o].lzy+=x;
  24.     }
  25.     inline void down(int o){
  26.         if(!T[o].lzy)return;
  27.         if(T[o].lc)plus(T[o].lc,T[o].lzy);
  28.         if(T[o].rc)plus(T[o].rc,T[o].lzy);
  29.         T[o].lzy=0;
  30.     }
  31.     inline void up(const int &o){
  32.         T[o].sz=T[T[o].lc].sz+1+T[T[o].rc].sz;
  33.         T[o].best=max(T[o].val,max(T[T[o].lc].best,T[T[o].rc].best));
  34.     }
  35.     inline int make(int x,int y){
  36.         if(!x||!y)return x|y;
  37.         down(x),down(y);
  38.         if(T[x].key<T[y].key){
  39.             T[x].rc=make(T[x].rc,y);
  40.             return up(x),x;
  41.         }
  42.         T[y].lc=make(x,T[y].lc);
  43.         return up(y),y;
  44.     }
  45.     pii split(int o,int k){
  46.         if(!o)return mp(0,0);
  47.         down(o);
  48.         if(k<T[o].tag){
  49.             pii y=split(T[o].lc,k);
  50.             T[o].lc=y.se,y.se=o;
  51.             return up(o),y;
  52.         }
  53.         pii y=split(T[o].rc,k);
  54.         T[o].rc=y.fi,y.fi=o;
  55.         return up(o),y;
  56.     }
  57.     int count(int &rt,int l,int r){
  58.         if(!rt)return 0;
  59.         //printf("@ %d %d %d\n",rt,l,r);
  60.         pii x=split(rt,l-1);
  61.         pii y=split(x.se,r);
  62.         int res=T[y.fi].sz;
  63.         rt=make(x.fi,make(y.fi,y.se));
  64.         return res;
  65.     }
  66.     int getmx(int &rt,int l,int r){
  67.         if(!rt)return 0;
  68.         pii x=split(rt,l-1);
  69.         pii y=split(x.se,r);
  70.         int res=T[y.fi].best;
  71.         rt=make(x.fi,make(y.fi,y.se));
  72.         return res;
  73.     }
  74.     void add(int &rt,int a,int b){
  75.         pii x=split(rt,a-1);
  76.         rt=make(x.fi,make(nw(a,b),x.se));
  77.     }
  78.     void chg(int &rt,int a,int b){
  79.         pii x=split(rt,a-1);
  80.         pii y=split(x.se,a);
  81.         down(y.fi),T[y.fi].val=b,up(y.fi);
  82.         rt=make(x.fi,make(y.fi,y.se));
  83.     }
  84.     int del(int &rt,int a){
  85.         pii x=split(rt,a-1);
  86.         pii y=split(x.se,a);
  87.         int res=T[y.fi].val;
  88.         push(y.fi);
  89.         rt=make(x.fi,y.se);
  90.         return res;
  91.     }
  92.     int find(int o,int k){
  93.         if(!o)return 0;
  94.         if(T[o].tag==k)return 1;
  95.         down(o);
  96.         if(k<T[o].tag)return find(T[o].lc,k);
  97.         return find(T[o].rc,k);
  98.     }
  99. }
  100. const int inf=1e6;
  101. const int M=1000000*25;
  102. namespace seg{
  103.     int lc[M],rc[M],cur[M],shit[M];
  104.     int stk[M],sz,top;
  105.     inline int nw(){
  106.         int o;
  107.         if(top)o=stk[top--];
  108.         else o=++sz;
  109.         lc[o]=rc[o]=cur[o]=shit[o]=0;
  110.         return o;
  111.     }
  112.     inline void push(int o){
  113.         stk[++top]=o;
  114.     }
  115.     void plus(int o,int x){
  116.         if(!o)return;
  117.         treap::plus(cur[o],x);
  118.         shit[o]+=x;
  119.     }
  120.     void down(int o){
  121.         if(!shit[o])return;
  122.         plus(lc[o],shit[o]);
  123.         plus(rc[o],shit[o]);
  124.         shit[o]=0;
  125.     }
  126.     #define mid ((l + r) >> 1)
  127.     int build(int l,int r,int p,int A,int B){
  128.         int o=nw();
  129.         treap::add(cur[o],p,B);
  130.         if(l==r)return o;
  131.         if(A<=mid)lc[o]=build(l,mid,p,A,B);
  132.         else rc[o]=build(mid+1,r,p,A,B);
  133.         return o;
  134.     }
  135.     int del(int o,int l,int r,int p){
  136.         if(!treap::find(cur[o],p))return 0;
  137.         down(o);
  138.         int owo=treap::del(cur[o],p);
  139.         if(l==r)return owo;
  140.         int tmp=del(lc[o],l,mid,p);
  141.         int tmp2=del(rc[o],mid+1,r,p);
  142.         return max(tmp,tmp2);
  143.     }
  144.     void ins(int &o,int l,int r,int p,int A,int B){
  145.         if(!o)o=nw();
  146.         down(o);
  147.         treap::add(cur[o],p,B);
  148.         if(l==r)return;
  149.         if(A<=mid)ins(lc[o],l,mid,p,A,B);
  150.         else ins(rc[o],mid+1,r,p,A,B);
  151.     }
  152.     void chgB(int o,int l,int r,int p,int nwB){
  153.         if(!treap::find(cur[o],p))return;
  154.         down(o);
  155.         treap::chg(cur[o],p,nwB);
  156.         if(l==r)return;
  157.         chgB(lc[o],l,mid,p,nwB);
  158.         chgB(rc[o],mid+1,r,p,nwB);
  159.     }
  160.     int merge(int x,int y,int l,int r){
  161.         down(x),down(y);
  162.         if(!x||!y)return x|y;
  163.         cur[x]=treap::make(cur[x],cur[y]);
  164.         if(l==r)return push(y),x;
  165.         lc[x]=merge(lc[x],lc[y],l,mid);
  166.         rc[x]=merge(rc[x],rc[y],mid+1,r);
  167.         return push(y),x;
  168.     }
  169.     int qryA(int o,int l,int r,int x,int y,int L,int R){
  170.         if(l==x&&y==r){
  171.             return treap::count(cur[o],L,R);
  172.         }
  173.         down(o);
  174.         if(y<=mid)return qryA(lc[o],l,mid,x,y,L,R);
  175.         if(mid<x)return qryA(rc[o],mid+1,r,x,y,L,R);
  176.         return qryA(lc[o],l,mid,x,mid,L,R)
  177.              + qryA(rc[o],mid+1,r,mid+1,y,L,R);
  178.     }
  179.     int qryB(int o,int l,int r,int K,int L,int R){
  180.         if(l==r)return l;
  181.         down(o);
  182.         int tmp=treap::count(cur[rc[o]],L,R);
  183.         //printf("%d %d  %d %d  %d\n",l,r,L,R,tmp);
  184.         if(K<=tmp)return qryB(rc[o],mid+1,r,K,L,R);
  185.         return qryB(lc[o],l,mid,K-tmp,L,R);
  186.     }
  187.     int qryC(int o,int l,int r,int x,int y,int L,int R){
  188.         if(l==x&&y==r)
  189.             return treap::getmx(cur[o],L,R);
  190.         down(o);
  191.         if(y<=mid)return qryC(lc[o],l,mid,x,y,L,R);
  192.         if(mid<x)return qryC(rc[o],mid+1,r,x,y,L,R);
  193.         return max(qryC(lc[o],l,mid,x,mid,L,R),
  194.                    qryC(rc[o],mid+1,r,mid+1,y,L,R));
  195.     }
  196.     #undef mid
  197. }

维护线段

需要一些分类讨论

  1. /**Treap**/
  2. int lc[N],rc[N],sz[N],key[N],L[N],R[N];
  3. int len[N],rev[N],lazy[N],rt,size;
  5. inline int nw(int l,int r){
  6.     int o=++size;
  7.     if(l<=r)L[o]=l,R[o]=r;
  8.     else L[o]=r,R[o]=l,rev[o]=1;
  9.     key[o]=rand(),sz[o]=len[o]=abs(r-l)+1;
  10.     return o;
  11. }
  12. inline void reverse(int o){
  13.     if(!o)return;
  14.     swap(lc[o],rc[o]);
  15.     lazy[o]^=1,rev[o]^=1;
  16. }
  17. inline void down(int o){
  18.     if(lazy[o]){
  19.         reverse(lc[o]);
  20.         reverse(rc[o]);
  21.         lazy[o]=0;
  22.     }
  23. }
  24. inline void up(int o){
  25.     sz[o]=sz[lc[o]]+len[o]+sz[rc[o]];
  26. }
  27. int make(int x,int y){
  28.     if(!x||!y)return x|y;
  29.     down(x),down(y);
  30.     if(key[x]<key[y]){
  31.         rc[x]=make(rc[x],y);
  32.         return up(x),x;
  33.     }
  34.     else{
  35.         lc[y]=make(x,lc[y]);
  36.         return up(y),y;
  37.     }
  38. }
  39. pii splitseg(int x,int k){
  40.     pii y;
  41.     if(!rev[x]){
  42.         y.fi=nw(L[x],L[x]+k-1);
  43.         y.se=nw(L[x]+k,R[x]);
  44.     }
  45.     else{
  46.         y.fi=nw(R[x],R[x]-k+1);
  47.         y.se=nw(R[x]-k,L[x]);
  48.     }
  49.     return y;
  50. }
  51. pii split(int x,int k){
  52.     if(!x)return mp(0,0);
  53.     if(!k)return mp(0,x);
  54.     if(k==sz[x])return mp(x,0);
  55.     down(x);
  56.     if(!lc[x]&&!rc[x])return splitseg(x,k);
  57.     pii y;
  58.     if(k<=sz[lc[x]]){
  59.         y=split(lc[x],k);
  60.         lc[x]=y.se,y.se=x;
  61.         return up(x),y;
  62.     }
  63.     else if(k>=len[x]+sz[lc[x]]){
  64.         y=split(rc[x],k-len[x]-sz[lc[x]]);
  65.         rc[x]=y.fi,y.fi=x;
  66.         return up(x),y;
  67.     }
  68.     else{
  69.         int LC=lc[x],RC=rc[x];
  70.         y=splitseg(x,k-sz[lc[x]]);
  71.         lc[y.fi]=LC,rc[y.se]=RC;
  72.         up(y.fi),up(y.se);
  73.         return y;
  74.     }
  75. }
  76. void Mov(int l,int r){
  77.     pii x=split(rt,l-1);
  78.     pii y=split(x.se,r-l+1);
  79.     rt=make(y.fi,make(x.fi,y.se));
  80. }
  81. void Rev(int l,int r){
  82.     pii x=split(rt,l-1);
  83.     //printf("# %d\n",sz[x.fi]);
  84.     pii y=split(x.se,r-l+1);
  85.     reverse(y.fi);
  86.     //printf("! %d %d\n",sz[y.fi],sz[y.se]);
  87.     rt=make(x.fi,make(y.fi,y.se));
  88.     //printf("@ %d\n",sz[rt]);
  89. }
  90. int clk;
  91. void print(int o){
  92.     if(!o)return;
  93.     down(o);
  94.     print(lc[o]);
  95.     if(!rev[o])v.pb(mp(L[o],R[o]));
  96.     else v.pb(mp(R[o],L[o]));
  97.     print(rc[o]);
  98. }

边分治与闵可夫斯基凸包合并

注意实现

  1. #include<bits/stdc++.h>
  2. #define rep(i,a,b) for(int i=(a);i<=(b);i++)
  3. #define per(i,a,b) for(int i=(a);i>=(b);i--)
  4. #define REP(i,n) for(int i=(0);i<(n);i++)
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define mp make_pair
  9. using namespace std;
  10. typedef pair<int,int> pii;
  11. typedef vector<int> vi;
  12. typedef long long lll;
  13. typedef long long ll;
  15. inline int read(){
  16.     char ch=getchar();int x=0,op=0;
  17.     while(!isdigit(ch))op|=(ch=='-'),ch=getchar();
  18.     while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
  19.     return op?-x:x;
  20. }
  22. const int N=200005;
  23. struct P{
  24.     ll x,y;
  25.     P(ll _x=0,ll _y=0){x=_x,y=_y;}
  26.     friend P operator + (const P &a,const P &b){
  27.         return P(a.x+b.x,a.y+b.y);
  28.     }
  29.     friend P operator - (const P &a,const P &b){
  30.         return P(a.x-b.x,a.y-b.y);
  31.     }
  32.     friend lll operator * (const P &a,const P &b){
  33.         return (lll)a.x*b.y-(lll)a.y*b.x;
  34.     }
  35.     inline ll f(const int &k){return k*x+y;}
  36. }emp;
  37. vector<pair<int,P>> g[N],e[N];
  38. vector<P> L,R,all;
  39. int n,m;
  41. void rebuild(int u,int fa){
  42.     vector<pair<int,P>> son;
  43.     for(auto v:g[u])
  44.         if(v.fi!=fa){
  45.             rebuild(v.fi,u);
  46.             son.pb(v);
  47.         }
  48.     int last=u,now;
  49.     for(auto v:son){
  50.         now=++n;
  51.         e[last].pb(mp(now,emp));
  52.         e[now].pb(mp(last,emp));
  53.         e[now].pb(mp(v.fi,v.se));
  54.         e[v.fi].pb(mp(now,v.se));
  55.         last=now;
  56.     }
  57. }
  59. void convex(vector<P> &p){
  60.     vector<P> res;
  61.     sort(p.begin(),p.end(),[&](const P &a,const P &b){
  62.         return a.x<b.x||a.x==b.x&&a.y>b.y;
  63.     });
  64.     int m=0;
  65.     REP(i,p.size()){
  66.         if(i&&p[i].x==p[i-1].x)continue;
  67.         while(m&&res[m-1].y<=p[i].y)
  68.             res.pop_back(),m--;
  69.         while(m>=2&&(p[i]-res[m-2])*(res[m-1]-res[m-2])<=0)
  70.             res.pop_back(),m--;
  71.         res.pb(p[i]),m++;
  72.     }
  73.     p=res;
  74. }
  75. void merge(){
  76.     all.pb(L[0]+R[0]);
  77.     for(int i=0,j=0;i+1<L.size()||j+1<R.size();)
  78.         if(j+1==R.size()||(i+1<L.size()&&(L[i+1]-L[i])
  79.                                         *(R[j+1]-R[j])<0))
  80.             all.pb(L[++i]+R[j]);
  81.         else
  82.             all.pb(L[i]+R[++j]);
  83. }
  85. P bas;
  86. int sz[N],vis[N],rt,prt;
  87. void find(int u,int fa,int s,P las){
  88.     sz[u]=1;
  89.     for(auto v:e[u])
  90.         if(v.fi!=fa&&!vis[v.fi]){
  91.             find(v.fi,u,s,v.se);
  92.             sz[u]+=sz[v.fi];
  93.         }
  94.     if(fa&&(!rt||max(sz[u],s-sz[u])<max(sz[rt],s-sz[rt])))
  95.         rt=u,prt=fa,bas=las;
  96. }
  97. void get(int u,int fa,vector<P> &p,P now){
  98.     p.pb(now);
  99.     for(auto v:e[u])
  100.         if(v.fi!=fa&&!vis[v.fi])
  101.             get(v.fi,u,p,now+v.se);
  102. }
  103. void divide(int x,int s){
  104.     if(s==1)return;
  105.     rt=0,find(x,0,s,emp);
  106.     int u=rt,v=prt;
  107.     int su=sz[u],sv=s-su;
  108.     L.clear(),get(u,v,L,emp);
  109.     R.clear(),get(v,u,R,bas);
  110.     convex(L),convex(R),merge();
  111.     vis[v]=1,divide(u,su),vis[v]=0;
  112.     vis[u]=1,divide(v,sv),vis[v]=0;
  113. }
  115. int main(){
  116.     n=read(),m=read();
  117.     if(n==1){
  118.         while(m--)puts("0");
  119.         return 0;
  120.     }
  121.     rep(i,1,n-1){
  122.         int u=read(),v=read();
  123.         int x=read(),y=read();
  124.         g[u].pb(mp(v,P(x,y)));
  125.         g[v].pb(mp(u,P(x,y)));
  126.     }
  127.     rebuild(1,0);
  128.     divide(1,n);
  129.     convex(all);
  130.     for(int i=0,j=0;i<m;i++){
  131.         while(j+1<all.size()&&all[j+1].f(i)>all[j].f(i))j++;
  132.         printf("%lld%c",all[j].f(i)," \n"[i==m-1]);
  133.     }
  134.     return 0;
  135. }

对询问分块

May holiday

可以暴力建虚树

  1. #include<bits/stdc++.h>
  2. #define rep(i,a,b) for (int i=(a); i<=(b); i++)
  3. #define per(i,a,b) for (int i=(a); i>=(b); i--)
  4. #define REP(i,n) for (int i=(0); i<(n); i++)
  5. #define clr(x) memset(x, 0, sizeof x)
  6. using namespace std;
  8. const int N = 100005, M = 500;
  9. int on[N], c[N], cur[N], ex[N], s[N], f[N];
  10. int p[N], t[N], q[N], h[N], pa[N];
  11. vector<pair<int,int> > v[N];
  12. vector<int> e[N];
  13. int n, m, ans;
  15. int clk;
  16. void dfs(int u, int fa) {
  17.     h[++clk] = u;
  18.     for (auto v : e[u])
  19.         if (v != fa) dfs(v, u);
  20. }
  22. int main() {
  23.     scanf("%d%d", &n, &m);
  24.     rep (i, 2, n) scanf("%d", &p[i]), e[p[i]].push_back(i);
  25.     dfs(1, 0);
  26.     rep (i, 1, n) scanf("%d", &t[i]);
  27.     rep (i, 1, m) scanf("%d", &q[i]);
  28.     for (int l = 1, r = min(M, m); l <= m; l = r + 1, r = min(r + M, m)) {
  29.         clr(on), clr(c);
  30.         rep (i, l, r) on[abs(q[i])] = 1;
  31.         per (i, n, 1) {
  32.             int x = h[i];
  33.             if (c[x] >= 2) on[x] = 1;
  34.             if (on[x] || c[x]) c[p[x]] ++;
  35.         }
  36.         rep (i, 1, n) {
  37.             int x = h[i];
  38.             if (on[p[x]]) pa[x] = p[x];
  39.             else pa[x] = pa[p[x]];
  40.         }
  42.         rep (i, 1, n) if (on[i]) {
  43.             vector<int> tmp;
  44.             for (int x = p[i]; x && !on[x]; x = p[x])
  45.                 if (!s[x]) tmp.push_back(t[x]);
  46.             sort(tmp.begin(), tmp.end());
  47.             for (int l = 0, r = 0; l < tmp.size(); l = r + 1, r = l) {
  48.                 while (r + 1 < tmp.size() && tmp[l] == tmp[r + 1]) r ++;
  49.                 v[i].push_back(make_pair(tmp[l], r - l + 1));
  50.             }
  51.             cur[i] = -1; ex[i] = 0;
  52.             while (cur[i] + 1 < v[i].size() && v[i][cur[i] + 1].first < 0)
  53.                 cur[i] ++;
  54.         }
  56.         rep (i, l, r) {
  57.             int u = abs(q[i]), op = q[i] / u;
  58.             if (t[u] < 0 && !s[u]) ans --;
  59.             s[u] += op;
  60.             if (t[u] < 0 && !s[u]) ans ++;
  61.             for (int x = u; x; x = pa[x]) {
  62.                 if (x != u) {
  63.                     if (t[x] < 0 && !s[x]) ans --;
  64.                     t[x] -= op;
  65.                     if (t[x] < 0 && !s[x]) ans ++;
  66.                 }
  67.                 ex[x] += op;
  68.                 while (cur[x] + 1 < v[x].size() 
  69.                     && v[x][cur[x] + 1].first - ex[x] < 0)
  70.                         ans += v[x][++cur[x]].second;
  71.                 while (cur[x] >= 0 
  72.                     && v[x][cur[x]].first - ex[x] >= 0)
  73.                         ans -= v[x][cur[x]--].second;
  74.             }
  75.             printf("%d ", ans);
  76.         }
  78.         clr(f);
  79.         rep (i, l, r) f[abs(q[i])] += (q[i] > 0 ? 1 : -1);
  80.         per (i, n, 1) {
  81.             int x = h[i];
  82.             f[p[x]] += f[x];
  83.         }
  84.         rep (i, 1, n) if (!on[i]) t[i] -= f[i];
  85.         rep (i, 1, n) if (on[i]) v[i].clear();
  86.     }
  87.     return 0;
  88. }

树分块

把链拆成两条会容易写很多

  1. #include<bits/stdc++.h>
  2. #define rep(i,a,b) for(int i=(a);i<=(b);++i)
  3. #define per(i,a,b) for(int i=(a);i>=(b);--i)
  4. #define REP(i,n) for(int i=(0);i<(n);++i)
  5. #define pb push_back
  6. using namespace std;
  7. typedef vector<int> vi;
  9. inline int read(){
  10.     char ch=getchar();int x=0,op=0;
  11.     while(!isdigit(ch))op|=(ch=='-'),ch=getchar();
  12.     while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
  13.     return op?-x:x;
  14. }
  16. const int N=100005,M=502;
  17. int in[N],out[N],fa[N],d[N],id[N],rt[N];
  18. int f[N][M],g[N][M],h[N][M];    //f     向上跳k步到达的点
  19. int n,Q,H,x,y,z;                //g     步长为k时，不离开块的步数
  20. vi e[N],w[N];                   //h     步长为k，到达的位置
  22. int clk;
  23. inline int isanc(int a,int b){
  24.     return in[a]<=in[b]&&out[b]<=out[a];
  25. }
  26. void dfs(int u,int dep=0){
  27.     in[u]=++clk,id[clk]=u;
  28.     if(!dep||dep==H-1||dep==H)dep=0,rt[u]=u;
  29.     REP(i,e[u].size())
  30.         if(e[u][i]!=fa[u]){
  31.             d[e[u][i]]=d[u]+w[u][i];
  32.             fa[e[u][i]]=u;
  33.             dfs(e[u][i],dep+w[u][i]);
  34.         }
  35.     out[u]=clk;
  36. }
  38. void init(){
  39.     fa[1]=1,dfs(1,0);
  40.     rep(i,1,n){
  41.         int u=id[i];
  42.         if(!rt[u])rt[u]=rt[fa[u]];
  43.     }
  44.     rep(i,1,n){
  45.         int u=id[i],v=u;
  46.         rep(j,1,H){
  47.             if(v>=2&&d[u]-d[fa[v]]<=j)v=fa[v];
  48.             f[u][j]=v;
  49.         }
  50.     }
  51.     rep(i,1,n){
  52.         int u=id[i],v;
  53.         rep(j,1,H){
  54.             v=f[u][j];
  55.             if(u==v||rt[v]!=rt[u]){
  56.                 g[u][j]=0,h[u][j]=u;
  57.             }
  58.             else{
  59.                 g[u][j]=g[v][j]+1;
  60.                 h[u][j]=h[v][j];
  61.             }
  62.         }
  63.     }   
  64. }
  66. int bf1(int x,int y,int k){ 
  67.     int res=0,nxt;
  68.     for(;k<=H;){
  69.         if(d[y]>d[x])swap(x,y);
  70.         nxt=f[x][k];
  71.         if(isanc(nxt,y))break;
  72.         res++,x=nxt;
  73.     }
  74.     int dist=0;
  75.     while(x!=y){
  76.         if(d[y]>d[x])swap(x,y);
  77.         dist+=d[x]-d[fa[x]],x=fa[x];
  78.     }
  79.     return res+1+(dist>k);
  80. }
  81. int solve1(int x,int y,int k){
  82.     int res=0,nxt;
  83.     while(x!=y){
  84.         if(d[y]>d[x])swap(x,y);
  85.         nxt=h[x][k];
  86.         if(isanc(nxt,y))return res+bf1(x,y,k);
  87.         res+=g[x][k],x=nxt;
  88.         if(x==y)break;
  89.         nxt=f[x][k];
  90.         if(isanc(nxt,y))return res+bf1(x,y,k);
  91.         res++,x=nxt;
  92.     }
  93.     return res;
  94. }
  96. int jump(int x,int k){
  97.     while(k&&x>=2){
  98.         if(x==rt[x]){
  99.             if(d[x]-d[fa[x]]<=k) 
  100.                 k-=d[x]-d[fa[x]],x=fa[x];
  101.             else return x;
  102.         }
  103.         else if(d[x]-d[rt[x]]<=k)
  104.             k-=d[x]-d[rt[x]],x=rt[x];
  105.         else return f[x][k];
  106.     }
  107.     return x;
  108. }
  109. int solve2(int x,int y,int k){
  110.     int res=0,nxt;
  111.     while(x!=y){
  112.         if(d[y]>d[x])swap(x,y);
  113.         nxt=jump(x,k);
  114.         if(isanc(nxt,y))return res+bf1(x,y,k);
  115.         res++,x=nxt;
  116.     }
  117.     return res;
  118. }
  120. int main(){
  121.     n=read();
  122.     H=max(2,(int)sqrt(n));
  123.     rep(i,1,n-1){
  124.         x=read(),y=read(),z=read();
  125.         e[x].pb(y),w[x].pb(z);
  126.         e[y].pb(x),w[y].pb(z);
  127.     }
  128.     init();
  129.     Q=read();
  130.     while(Q--){
  131.         x=read(),y=read(),z=read();
  132.         if(z<=H)printf("%d\n",solve1(x,y,z));
  133.         else printf("%d\n",solve2(x,y,z));
  134.     }
  135.     return 0;
  136. }

小技巧

zkw 线段树

能够有效减小常数。适用于单点修改，区间查询的简单信息维护。

  1. namespace seg {
  2.     const int b = 1<<18; int t[(1<<19)+5];
  3.     inline void init() { memset(t, 0x3f, sizeof t); }
  4.     inline void u(int x, int v) {
  5.         for (t[x+=b]=v, x>>=1; x; x>>=1)
  6.             t[x] = min(t[x<<1], t[x<<1|1]);
  7.     }
  8.     inline int q(int l, int r) {
  9.         int ans = inf;
  10.         for (l+=b-1, r+=b+1; l^r^1; l>>=1, r>>=1) {
  11.             if (~l&1) cmin(ans, t[l^1]);
  12.             if ( r&1) cmin(ans, t[r^1]);
  13.         }
  14.         return ans;
  15.     }
  16. }

减少堆的常数

使用C语言的函数，略快于priority_queue

  1. struct PQ {
  2.     node a[N * 5]; int w;
  3.     inline void push(const node &x) {
  4.         a[++w] =  x; push_heap(a + 1, a + w + 1);
  5.     }
  6.     inline void pop() {
  7.         pop_heap(a + 1, a + w + 1); --w;
  8.     }
  9.     inline const node& top() {
  10.         return a[1];
  11.     }
  12. } Q;

李超树

只需要支持插入线段，单点求最值。特别好写

  1. struct L{
  2.     ll k,b;
  3.     L(ll _k=0,ll _b=-1e18){k=_k,b=_b;}
  4.     ll operator () (ll x){return k*x+b;}
  5. };
  6. struct seg{
  7.     L x;seg *lc,*rc;
  8.     seg():x(){lc=rc=0;};
  9.     void add(L y,ll l=0,ll r=1e9){
  10.         ll m=(l+r)>>1;
  11.         if(y(m)>x(m))swap(x,y);
  12.         if(x(l)<y(l)){
  13.             if(!lc)lc=new seg;
  14.             lc->add(y,l,m);
  15.         }
  16.         else if(x(r)<y(r)){
  17.             if(!rc)rc=new seg;
  18.             rc->add(y,m+1,r);
  19.         }
  20.     }
  21.     ll qry(ll k,ll l=0,ll r=1e9){
  22.         ll res=x(k),m=(l+r)>>1;
  23.         if(k<=m&&lc)res=max(res,lc->qry(k,l,m));
  24.         if(k>m&&rc)res=max(res,rc->qry(k,m+1,r));
  25.         return res;
  26.     }
  27. }s,t;

数据结构拆分在namespace与struct中

例如树链上维护分块，或者SAM嵌套数据结构。拆分出来是一个很好的选择，减少调试难度。

同时可以结合指针动态开辟。

  2. struct block{
  3.     int *pre,*suf,sz,L,R,ans,tag;
  4.     pii *a,*b,*c;
  5.     inline void doit(int flag){
  6.         if(flag){
  7.             pre[1]=0,suf[0]=1;
  8.             pre[sz+1]=sz,suf[sz]=sz+1;
  9.             ans=1;
  10.             rep(i,2,sz)
  11.                 if(a[i].fi!=a[i-1].fi)pre[i]=i-1;
  12.                 else pre[i]=pre[i-1];
  13.             per(i,sz-1,1)
  14.                 if(a[i].fi!=a[i+1].fi)suf[i]=i+1;
  15.                 else suf[i]=suf[i+1];
  16.         }
  17.         while(ans<=sz&&a[ans].fi+tag<=0)
  18.             ans=suf[ans];
  19.         while(pre[ans]&&a[pre[ans]].fi+tag>0)
  20.             ans=pre[pre[ans]]+1;
  21.     }
  22.     void build(int l,int r){
  23.         L=l,R=r,sz=r-l+1;
  24.         a=new pii[sz+3];
  25.         b=new pii[sz+3];
  26.         c=new pii[sz+3];
  27.         pre=new int[sz+3];
  28.         suf=new int[sz+3];
  29.         rep(i,1,sz)
  30.             a[i]=mp(w[id[l-1+i]],l-1+i);
  31.         sort(a+1,a+sz+1);
  32.         tag=ans=0,doit(1);
  33.     }
  34.     void upd(int l,int r,int ex){
  35.         if(l==L&&r==R)
  36.             return tag+=ex,doit(0);
  37.         int n=0,m=0,p=1,q=1,owo=1;
  38.         rep(i,1,sz)
  39.             if(l<=a[i].se&&a[i].se<=r)
  40.                 b[++n]=mp(a[i].fi+ex+tag,a[i].se);
  41.             else
  42.                 c[++m]=mp(a[i].fi+tag,a[i].se);
  43.         while(p<=n||q<=m)
  44.             if(p<=n&&(q>m||b[p]<c[q]))a[owo++]=b[p++];
  45.             else a[owo++]=c[q++];
  46.         tag=ans=0,doit(1);
  47.     }
  48.     int qry(int l,int r){
  50.         if(l==L&&r==R)return sz-ans+1;
  51.         int res=0;
  52.         rep(i,1,sz)if(l<=a[i].se&&a[i].se<=r)
  53.             res+=((a[i].fi+tag)>0);
  54.         return res;
  55.     }
  56. }b[N];

ST表支持O(1)回答LCA

  1. namespace Dis {
  2.     vector<pii> e[maxn];
  3.     int d[maxn], id[maxn], f[maxn<<1][lg], Lg[maxn<<1], n, clk;
  4.     inline void init(int _n) { n = _n; }
  5.     inline void link(int a, int b, int c) {
  6.         e[a].pb(mp(b, c));
  7.         e[b].pb(mp(a, c));
  8.     }
  9.     void dfs(int u, int fa) {
  10.         f[id[u] = ++clk][0] = d[u];
  11.         REP (i, e[u].size()) 
  12.             if (e[u][i].fi != fa) {
  13.                 d[e[u][i].fi] = d[u] + e[u][i].se;
  14.                 dfs(e[u][i].fi, u);
  15.                 f[++clk][0] = d[u];
  16.             }
  17.     }
  18.     void prepare() {
  19.         memset(f, 0x3f, sizeof f);
  20.         dfs(1, 0); Lg[0] = -1;
  21.         rep (i, 1, clk) Lg[i] = Lg[i>>1] + 1;
  22.         rep (i, 1, 18) rep (j, 1, clk - (1 << i))
  23.             f[j][i] = min(f[j][i-1], f[j+(1<<(i-1))][i-1]);
  24.     }
  25.     inline int ask(int a, int b) {
  26.         static int t, res; res = d[a] + d[b];
  27.         a = id[a]; b = id[b];
  28.         if (a > b) swap(a, b); t = Lg[b-a+1];
  29.         return res - 2 * min(f[a][t], f[b-(1<<t)+1][t]);
  30.     }
  31. }

数论

Min_25筛

  1. void init(int lim){
  2.     rep(i,2,lim){
  3.         if(!flag[i])p[++cnt]=i,sp[cnt]=(sp[cnt-1]+i)%mod;
  4.         for (int j=1;j<=cnt&&i*p[j]<=lim;++j){
  5.             flag[i*p[j]]=1;
  6.             if(i%p[j]==0)break;
  7.         }
  8.     }
  9. }
  11. inline int id(ll x){
  12.     return x<=T?b[x]:c[n/x];
  13. }
  14. void G(){
  15.     for (ll last=1,i;last<=n;last=i+1){
  16.         i=n/(n/last);a[++m]=n/i;
  17.         if(a[m]<=T)b[a[m]]=m;
  18.         else c[n/a[m]]=m;
  19.         h[m]=(a[m]-1)%mod;
  20.         g[m]=1ll*h[m]*(h[m]+3)%mod;
  21.         if(g[m]&1)g[m]+=mod;g[m]>>=1;
  22.     }
  23.     rep(j,1,cnt)
  24.         for(int i=1;i<=m&&a[i]>=1ll*p[j]*p[j];++i){
  25.             h[i]=(h[i]-(h[id(a[i]/p[j])]-(j-1)+mod)%mod+mod)%mod;
  26.             g[i]=(g[i]-1ll*p[j]*(g[id(a[i]/p[j])]-sp[j-1]+mod)%mod+mod)%mod;
  27.         }
  28. }
  30. int S(ll n,int k){
  31.     if(n<=1||p[k]>n)return 0;
  32.     int t=id(n);
  33.     ll res=(ll)g[t]-h[t]-(sp[k-1]-(k-1));
  34.     if(k==1)res+=2;
  35.     for(int i=k;i<=cnt&&1ll*p[i]*p[i]<=n;++i){
  36.         ll p1=p[i],p2=p1*p1;
  37.         for(int e=1;p2<=n;++e,p1=p2,p2*=p[i])
  38.             res+=(1ll*(p[i]^e)*S(n/p1,i+1)+(p[i]^(e+1)))%mod;
  39.     }
  40.     res%=mod;
  41.     //printf("%lld %d %d\n", n, k, res);
  42.     return res<0?res+mod:res;
  43. }

网络流

最大流

  1. const int N=1005,M=100005,inf=1e9;
  2. struct edge{int u,v,f,c;};
  3. struct ISAP{
  4.     int n,m,s,t;ll res;
  5.     int num[N],cur[N],d[N];
  6.     int link[M],h[N],p[N];
  7.     edge e[M];
  8.     inline void init(int _n){
  9.         n=_n,m=0,res=0;
  10.         memset(h,-1,sizeof h);
  11.         memset(cur,-1,sizeof cur);
  12.     }
  13.     inline void add(int u,int v,int w){
  14.         e[m]=(edge){u,v,0,w};
  15.         link[m]=h[u],cur[u]=h[u]=m++;
  16.         e[m]=(edge){v,u,0,0};
  17.         link[m]=h[v],cur[v]=h[v]=m++;
  18.     }
  19.     inline int aug(){
  20.         int mn=inf;
  21.         for(int x=t;x!=s;x=e[p[x]].u)
  22.             mn=min(mn,e[p[x]].c-e[p[x]].f);
  23.         for(int x=t;x!=s;x=e[p[x]].u)
  24.             e[p[x]].f+=mn,e[p[x]^1].f-=mn;
  25.         return mn;
  26.     }
  27.     int Maxflow(int _s,int _t){
  28.         int u=_s;s=_s,t=_t;
  29.         memset(num,0,sizeof num);
  30.         memset(d,0,sizeof d),num[0]=n;
  31.         while(d[s]<n){
  32.             if(u==t)res+=aug(),u=s;
  33.             int flag=0;
  34.             loop(k,cur[u])
  35.                 if(e[k].f<e[k].c&&d[u]==d[e[k].v]+1){
  36.                     cur[u]=k,p[u=e[k].v]=k;
  37.                     flag=1;break;
  38.                 }
  39.             if(flag)continue;
  40.             int mn=n;
  41.             loop(k,cur[u]=h[u])if(e[k].f<e[k].c)
  42.                 mn=min(mn,d[e[k].v]+1);
  43.             if(!(--num[d[u]]))return res;
  44.             num[d[u]=mn]++,u=(u==s?s:e[p[u]].u);
  45.         }
  46.         return res;
  47.     }
  48. }G;

KM算法

背模板！！

  1. #include<bits/stdc++.h>
  2. #define rep(i,a,b) for(int i=(a);i<=(b);i++)
  3. #define per(i,a,b) for(int i=(a);i>=(b);i--)
  4. #define REP(i,n) for(int i=(0);i<(n);i++)
  5. using namespace std;
  7. const int N=405,inf=1e9+99;
  8. int w[N][N],ex[N],ey[N],mn[N];
  9. int vx[N],vy[N],cur[N],p[N];
  10. int n,m,K,a,b,c;
  12. int dfs(int x){
  13.     vx[x]=1;
  14.     rep(y,1,n)if(!vy[y]){
  15.         int d=ex[x]+ey[y]-w[x][y];
  16.         if(!d){
  17.             vy[y]=1;
  18.             if(!cur[y]||dfs(cur[y]))
  19.                 return cur[y]=x,1;
  20.         }
  21.         else mn[y]=min(mn[y],d);
  22.     }
  23.     return 0;
  24. }
  25. long long KM(){
  26.     rep(x,1,n)rep(y,1,n)
  27.         ex[x]=max(ex[x],w[x][y]);
  28.     rep(x,1,n){
  29.         rep(y,1,n)mn[y]=inf;
  30.         memset(vx,0,sizeof vx);
  31.         memset(vy,0,sizeof vy);
  32.         if(dfs(x))continue;
  33.         for(;;){
  34.             int d=inf,t=0;
  35.             rep(y,1,n)if(!vy[y])d=min(d,mn[y]);
  36.             rep(x,1,n)if(vx[x])ex[x]-=d;
  37.             rep(y,1,n)if(vy[y])ey[y]+=d;
  38.             else if(!(mn[y]-=d))t=y;
  39.             if(!cur[t])break;
  40.             int e=cur[t];vx[e]=vy[t]=1;
  41.             rep(y,1,n)mn[y]=min(mn[y],ex[e]+ey[y]-w[e][y]);
  42.         }
  43.         memset(vx,0,sizeof vx);
  44.         memset(vy,0,sizeof vy);
  45.         dfs(x);
  46.     }
  47.     long long ans=0;
  48.     rep(y,1,n)ans+=w[cur[y]][y],p[cur[y]]=y;
  49.     return ans;
  50. }
  52. int main(){
  53.     scanf("%d%d%d",&n,&m,&K);
  54.     swap(n,m),n=max(n,m);
  55.     rep(i,1,K){
  56.         scanf("%d%d%d",&a,&b,&c);
  57.         w[a][b]=c;
  58.     }
  59.     cout<<KM()<<endl;
  60.     rep(i,1,m)
  61.         if(w[i][p[i]]>0)printf("%d ",p[i]);
  62.         else putchar('0'),putchar(' ');
  63.     return 0;
  64. }

原始对偶费用流

由于稠密图访问的连续性，用vector可能会快很多

  1. const int N=10005,M=300005,inf=1e9+99;
  2. namespace G{    //注意只支持非负边权，否则需要spfa预处理
  3.     #define real d[u]+f[u]-f[t.v]
  4.     struct edge{int u,v,w,f,c,p;};vector<edge>e[N];
  5.     int d[N],f[N],s,t,n,m;
  6.     inline void init(int _n,int _s=0,int _t=0){
  7.         n=_n,s=(_s?_s:1),t=(_t?_t:n),m=0;
  8.     }
  9.     inline void add(int u,int v,int c,int w){
  10.         e[u].pb((edge){u,v,w,0,c,(int)e[v].size()});
  11.         e[v].pb((edge){v,u,-w,0,0,(int)e[u].size()-1});
  12.     }
  13.     struct node{
  14.         int d,v;
  15.         friend bool operator < (const node &a,const node &b){
  16.             return a.d>b.d;
  17.         }
  18.     };priority_queue<node>Q;
  19.     bool dij(){
  20.         rep(i,1,n){
  21.             f[i]=min(f[i]+d[i],inf);
  22.             d[i]=i==s?0:inf;
  23.         }
  24.         Q.push((node){0,s});
  25.         while(!Q.empty()){
  26.             int t=Q.top().d,u=Q.top().v;
  27.             Q.pop();if(t>d[u])continue;
  28.             REP(k,e[u].size()){
  29.                 edge &t=e[u][k];
  30.                 if(t.f<t.c&&real+t.w<d[t.v])
  31.                     Q.push((node){d[t.v]=real+t.w,t.v});
  32.             }
  33.         }
  34.         return d[t]<inf;
  35.     }
  36.     int r[N],in[N];
  37.     int dfs(int u,int a){
  38.         if(u==t)return a;
  39.         int res=0;in[u]=1;
  40.         for(int &k=r[u];k<e[u].size();k++){
  41.             edge &t=e[u][k];
  42.             if(t.f<t.c&&real+t.w==d[t.v]&&!in[t.v]){
  43.                 int now=dfs(t.v,min(a,t.c-t.f));
  44.                 t.f+=now,e[t.v][t.p].f-=now,res+=now;
  45.                 if(!(a-=now))break;
  46.             }
  47.         }
  48.         return in[u]=0,res;
  49.     }
  50.     void mcmf(int &flow,int &cost){
  51.         int now;
  52.         while(dij()){
  53.             rep(i,1,n)r[i]=0;
  54.             flow+=(now=dfs(s,inf));
  55.             cost+=now*(d[t]+f[t]);
  56.         }
  57.     }
  58. }

字符串

后缀自动机

用途：构造后缀树，后缀树上可以DP，LCT维护..

NOI 2015 品酒大会

  1. namespace sam{
  2.     int t[N][26],fa[N],buf[N],mx[N],pos[N],a[N],tail=1,size=1;
  3.     ll sz[N],f[N],g[N],cnt[N],ans[N];
  4.     vi e[N],w[N];
  5.     int nw(int val){
  6.         return mx[++size]=val,f[size]=-inf,g[size]=inf,size;
  7.     }
  8.     void ins(int c,int id,int val){
  9.         int p=tail,np=nw(mx[p]+1);
  10.         pos[id]=np,f[np]=g[np]=val,sz[np]=1;
  11.         for(;!t[p][c];p=fa[p])t[p][c]=np;
  12.         if(!p)return(void)(fa[np]=1,tail=np);
  13.         int q=t[p][c];
  14.         if(mx[q]==mx[p]+1)fa[np]=q;
  15.         else{
  16.             int nq=nw(mx[p]+1);
  17.             fa[nq]=fa[q],fa[q]=fa[np]=nq;
  18.             REP(k,26)t[nq][k]=t[q][k];
  19.             for(;p&&t[p][c]==q;p=fa[p])t[p][c]=nq;
  20.         }
  21.         tail=np;
  22.     }
  23.     void init(){
  24.         f[1]=-inf,g[1]=inf;
  25.         rep(i,1,size)buf[mx[i]]++;
  26.         rep(i,1,size)buf[i]+=buf[i-1];
  27.         rep(i,1,size)a[buf[mx[i]]--]=i;
  28.         rep(i,2,size){
  29.             int u=a[i];
  30.             e[fa[u]].pb(u);
  31.             w[fa[u]].pb(mx[u]-mx[fa[u]]);
  32.         }
  33.     }
  34.     void dfs(int u,int d){
  35.         REP(i,e[u].size()){
  36.             dfs(e[u][i],d+w[u][i]);
  37.             cnt[d]+=1ll*sz[u]*sz[e[u][i]];
  38.             sz[u]+=sz[e[u][i]];
  39.             if(f[u]>-inf)
  40.                 ans[d]=max(ans[d],1ll*f[u]*f[e[u][i]]);
  41.             f[u]=max(f[u],f[e[u][i]]);
  42.             if(g[u]<inf)
  43.                 ans[d]=max(ans[d],1ll*g[u]*g[e[u][i]]);
  44.             g[u]=min(g[u],g[e[u][i]]);
  45.         }
  46.     }
  47.     void solve(int n){
  48.         rep(i,0,n)ans[i]=-1ll*inf*inf;
  49.         dfs(1,0);
  50.         per(i,n-1,0){
  51.             cnt[i]+=cnt[i+1];
  52.             ans[i]=max(ans[i],ans[i+1]);
  53.         }
  54.         rep(i,0,n-1)
  55.             printf("%lld %lld\n",cnt[i],!cnt[i]?0:ans[i]);
  56.     }
  57. }

SAM与dus on tree

绝佳搭档~

  1. const int N=1200005;
  2. namespace tool{
  3.     int c[N],S[N],len,tot;
  4.     set<int>::iterator i,j;
  5.     set<int> s;
  6.     #define lowbit(x) (x&-x)
  7.     inline void update(int c[],int x,int y){
  8.         for(;x<=len;x+=lowbit(x))c[x]+=y;
  9.     }
  10.     inline int query(int c[],int x){
  11.         int res=0;
  12.         for(;x;x-=lowbit(x))res+=c[x];
  13.         return res;
  14.     }
  15.     int qry(int k){
  16.         return k*(tot-query(c,k))+query(S,k);
  17.     }
  18.     void upd(int l,int op){
  19.         l=(l+len)%len;if(l==0)l=len;
  20.         update(c,l,op),tot+=op;
  21.         update(S,l,op*l);
  22.     }
  23.     void add(int p,int op){
  24.         if(op==1)s.insert(p);
  25.         else s.erase(p);
  26.         if(s.empty()||op==1&&s.size()==1)
  27.             return upd(0,op);
  28.         j=s.upper_bound(p);
  29.         if(j==s.end())j=s.begin();
  30.         i=s.lower_bound(p);
  31.         if(i==s.begin())i=s.end();--i;
  32.         upd(*j-*i,-op);
  33.         upd(*j-p,op),upd(p-*i,op);
  34.     }
  35. }
  36. int ans[N];
  37. namespace sam{
  38.     int t[N][26],fa[N],mx[N],owo[N];
  39.     int sz[N],sn[N],f[N][24];
  40.     int size=1,tail=1,clk;
  41.     vector<pii> q[N];
  42.     vi e[N];int id[N];
  43.     void init(){tail=1;}
  44.     inline int nw(int x,int y=0){
  45.         return mx[++size]=x,owo[size]=y,size;
  46.     }
  47.     int ins(int c,int val=0){
  48.         int p=tail,np=nw(mx[p]+1,val);
  49.         for(;p&&!t[p][c];p=fa[p])t[p][c]=np;
  50.         if(!p)return fa[np]=1,tail=np;
  51.         int q=t[p][c];
  52.         if(mx[q]==mx[p]+1)fa[np]=q;
  53.         else{
  54.             int nq=nw(mx[p]+1);
  55.             fa[nq]=fa[q],fa[q]=fa[np]=nq;
  56.             REP(k,26)t[nq][k]=t[q][k];
  57.             for(;p&&t[p][c]==q;p=fa[p])t[p][c]=nq;
  58.         }
  59.         return tail=np;
  60.     }
  61.     void predfs(int u){
  62.         sz[u]=1,id[++clk]=u;
  63.         rep(i,1,23)f[u][i]=f[f[u][i-1]][i-1];
  64.         for(auto v:e[u]){
  65.             f[v][0]=u,predfs(v),sz[u]+=sz[v];
  66.             if(sz[v]>sz[sn[u]])sn[u]=v;
  67.         }
  68.     }
  69.     void build(){
  70.         rep(i,2,size)e[fa[i]].pb(i);
  71.         predfs(1);
  72.     }
  73.     void add(int len,int p,int k,int id){
  74.         per(i,23,0)
  75.             if(mx[f[p][i]]>=len)p=f[p][i];
  76.         q[p].pb(mp(k,id));
  77.     }
  78.     void doit(int u,int ty){
  79.         if(owo[u]&&ty)tool::add(owo[u],1);
  80.         if(owo[u]&&!ty)tool::add(owo[u],-1);
  81.         for(auto v:e[u])doit(v,ty);
  82.     }
  83.     void solve(int u){
  84.         for(auto v:e[u])if(v!=sn[u])
  85.             solve(v),doit(v,0);
  86.         if(sn[u])solve(sn[u]);
  87.         for(auto v:e[u])if(v!=sn[u])
  88.             doit(v,1);
  89.         if(owo[u])tool::add(owo[u],1);
  90.         for(auto p:q[u])
  91.             ans[p.se]=tool::qry(p.fi);
  92.     }
  93. }

后缀数组

用途：快速比较LCP，经常配合ST表使用。几乎都可以被SAM代替。

NOI2016 优秀的拆分

求所有形如 的子串拆分数。

注意：多组数据，数组及时清空。

  1. #include<bits/stdc++.h>
  2. #define rep(i,a,b) for (int i=(a); i<=(b); i++)
  3. #define per(i,a,b) for (int i=(a); i>=(b); i--)
  4. #define clr(x) memset(x, 0, sizeof x)
  5. using namespace std;
  7. const int maxn = 60005;
  8. int SA[maxn], rank[maxn], height[maxn], tmp[maxn], tax[maxn];
  9. int pre[maxn], suf[maxn], f[maxn][20], lg[maxn], n, m, l, r;
  10. char s[maxn]; long long ans;
  12. inline bool cmp(int a[maxn], int x, int y, int w) {
  13.     return a[x] == a[y] && a[x+w] == a[y+w];
  14. }
  16. void Sort(int n, int m) {
  17.     rep (i, 0, m) tax[i] = 0;
  18.     rep (i, 1, n) tax[rank[i]]++;
  19.     rep (i, 1, m) tax[i] += tax[i-1];
  20.     per (i, n, 1) SA[tax[rank[tmp[i]]]--] = tmp[i];
  21. }
  23. void SuffixArray(char s[maxn], int n) {
  24.     clr(height); clr(rank); clr(tmp); clr(SA);
  25.     rep (i, 1, n) { rank[i] = s[i]; tmp[i] = i; }
  26.     m = 127; Sort(n, m);
  27.     for (int w=1,p=0,i; w<n; w+=w,m=p,p=0) {
  28.         rep (i, n-w+1, n) tmp[++p] = i;
  29.         rep (i, 1, n) if (SA[i] > w) tmp[++p] = SA[i] - w;
  30.         Sort(n, m); swap(tmp, rank); rank[SA[1]] = p = 1;
  31.         rep (i, 2, n) rank[SA[i]] = (cmp(tmp, SA[i-1], SA[i], w) ? p : ++p);
  32.     }
  33.     for (int i=1,j,k=0; i<=n; height[rank[i++]]=k)
  34.         for (k=k?k-1:k,j=SA[rank[i]-1]; s[i+k]==s[j+k]; k++);
  35. }
  37. void pre_ST(int n, int a[maxn]) {
  38.     clr(f); lg[1] = 0;
  39.     rep (i, 2, n) lg[i] = lg[i>>1] + 1;
  40.     rep (i, 1, n) f[i][0] = a[i];
  41.     rep (j, 1, 18) rep (i, 1, n) 
  42.         if (i+(1<<(j-1)) > n) f[i][j] = f[i][j-1];
  43.         else f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]);
  44. }
  46. inline int query(int l, int r) {
  47.     int t = lg[r - l + 1];
  48.     return min(f[l][t], f[r-(1<<t)+1][t]);
  49. }
  51. inline int getLCP(int x, int y) {
  52.     if (rank[x] > rank[y]) swap(x, y);
  53.     return query(rank[x]+1, rank[y]);
  54. }
  56. inline int revLCP(int x, int y) {
  57.     x = 2*n+2-x; y = 2*n+2-y;
  58.     if (rank[x] > rank[y]) swap(x, y);
  59.     return query(rank[x]+1, rank[y]);
  60. }
  62. int main() {
  63.     int T; scanf("%d", &T);
  64.     while (T--) {
  65.         clr(s); scanf("%s", s + 1); n = strlen(s + 1);
  66.         rep (i, 1, n) s[2*n+2-i] = s[i]; s[n+1] = '#';
  67.         SuffixArray(s, 2*n+1); pre_ST(2*n+1, height);
  68.         clr(pre); clr(suf); 
  69.         rep (L, 1, n) rep (p, 1, n/L-1) {
  70.             l = min(revLCP(p*L, p*L+L), L);
  71.             r = min(getLCP(p*L, p*L+L), L);
  72.             if (r+l-1 < L) continue;
  73.             pre[p*L+L-l+1+L-1]++; pre[p*L+L+r]--;
  74.             suf[p*L-l+1]++; suf[p*L+r-1-L+1+1]--;
  75.         }
  76.         ans = 0;
  77.         rep (i, 1, n) {
  78.             pre[i] += pre[i-1]; suf[i+1] += suf[i];
  79.             ans += 1LL * pre[i] * suf[i+1];
  80.         }
  81.         printf("%lld\n", ans);
  82.     }
  83.     return 0;
  84. }

图论

圆方树处理点双

注意链上可能需要特判LCA

  1. void tj(int u, int f) {
  2.     dfn[u] = low[u] = ++c; st[++tp] = u;
  3.     for (int k=G.h[u]; k; k=G.l[k]) if (G.v[k] != f)
  4.         if (!dfn[G.v[k]]) {
  5.             tj(G.v[k], u);
  6.             cmin(low[u], low[G.v[k]]);
  7.             if (low[G.v[k]] >= dfn[u]) {
  8.                 w[++t] = inf; T.A(u, t);
  9.                 do T.A(st[tp], t); while (st[tp--] != G.v[k]);
  10.             }
  11.         }
  12.         else cmin(low[u], dfn[G.v[k]]);
  13. }

其他

一般图最大匹配的随机化做法

又短又好写

  1. #include<bits/stdc++.h>
  2. #define rep(i,a,b) for(int i=(a);i<=(b);i++)
  3. #define per(i,a,b) for(int i=(a);i>=(b);i--)
  4. #define REP(i,n) for(int i=(0);i<(n);i++)
  5. #define pb push_back
  6. using namespace std;
  7. typedef vector<int> vi;
  9. const int N=505;
  10. int cur[N],vis[N],r[N],tim,n,m,ans,a,b;
  11. vi e[N];
  13. int dfs(int x){
  14.     if(!x)return 1;
  15.     vis[x]=tim;
  16.     vi::iterator it=e[x].begin();
  17.     vi::iterator ti=e[x].end();
  18.     random_shuffle(it,ti);
  19.     for(int u,v;it!=ti;it++){
  20.         u=*it,v=cur[u];
  21.         if(vis[v]<tim){
  22.             cur[x]=u,cur[u]=x,cur[v]=0;
  23.             if(dfs(v))return 1;
  24.             cur[u]=v,cur[v]=u,cur[x]=0;
  25.         }
  26.     }
  27.     return 0;
  28. }
  29. int main(){
  30.     scanf("%d%d",&n,&m);
  31.     while(m--){
  32.         scanf("%d%d",&a,&b);
  33.         e[a].pb(b),e[b].pb(a);
  34.     }
  35.     srand(time(NULL) ^ (long int)(new char));
  36.     rep(i,1,n)r[i]=i;
  37.     rep(T,1,3){
  38.         random_shuffle(r+1,r+n+1);
  39.         rep(i,1,n)if(!cur[r[i]])tim++,ans+=dfs(r[i]);
  40.     }
  41.     printf("%d\n",ans);
  42.     rep(i,1,n)printf("%d ",cur[i]);
  43.     return 0;
  44. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注