【模板】KMP字符串匹配

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 char a1[2000000],a2[2000000]; 9 int kmp[2000000];10 int main()11 {12 scanf("%s%s",a1,a2);13 kmp[0]=kmp[1]=0;//前一位，两位失配了，都只可能将第一位作为新的开头14 int len1=strlen(a1),len2=strlen(a2);15 int k;16 k=0;17 for(int i=1;i
          
         
        
       
      
     

【模板】ST表(线段树做的)

1 #include
     
       2 using namespace std; 3 const int maxn=1e5+5; 4 struct node{ 5     int l; 6     int r; 7     int maxx; 8 }t[maxn*3]; 9 int n,m,a[maxn];10 11 inline void read(int& x)12 {13    x=0;14    register char f=getchar(),c=0;15    while(!isdigit(f)&&f!='-')f=getchar();if(f=='-')c=1,f=getchar();16    while(isdigit(f))x=x*10+(f^48),f=getchar();if(c)x=~x+1;17 }18 19 inline void pushup(int x)20 {21     t[x].maxx=max(t[x<<1].maxx,t[x<<1|1].maxx);22 }23 24 void bt(int x,int l,int r)25 {26     t[x].l=l;27     t[x].r=r;28     if(l==r)29     {30         t[x].maxx=a[l];31         return ;32     }33     int mid=(l+r)>>1;34     bt(x<<1,l,mid);35     bt(x<<1|1,mid+1,r);36     pushup(x);37 }38 39 int query(int x,int r,int l)40 {41     if(t[x].l>=l&&t[x].r<=r)42     {43         return t[x].maxx;44     }45     if(t[x].l>r||t[x].r
     

【模板】并查集

1 #include
     
       2 using namespace std; 3 int n,m,z,x,y;  4 int father[10002]; 5 inline int find(int i) 6 { 7     if(i==father[i]) 8         return i; 9     while(i!=father[i])10         i=father[i];11     return father[i];12 }13 inline void unionn(int i,int j)14 {15     int r1=find(i);16     int r2=find(j);17     if(r1==r2)18         return ;19     father[r2]=r1;20     father[j]=r1;21     return ;22 }23 int main()24 {25     cin>>n>>m;26     for(int i=1 ; i<=n ; i++)27     father[i]=i;28     for(int i=1 ; i<=m ; i++)29     {30         cin>>z>>x>>y;31         switch(z)32         {33             case 1:34             {35                    unionn(x,y);36                 break;37             }38             case 2:39             {40                 if(find(x)==find(y))41                     cout<<"Y"<
     

【模板】堆

1 #include
     
       2 using namespace std; 3  4 inline void read(int& x) 5 { 6    x=0; 7    register char f=getchar(),c=0; 8    while(!isdigit(f)&&f!='-')f=getchar();if(f=='-')c=1,f=getchar(); 9    while(isdigit(f))x=x*10+(f^48),f=getchar();if(c)x=~x+1;10 }11 //默认排序是从大到小 12 priority_queue
      
       
        ,greater
        
          > q;//less是从大到小，greater是从小到大。 13 int a,b,n;14  15 int main()16 {17     read(n);18     for(int i=1;i<=n;i++)19     {20         read(a);21         if(a==1)22         {23             read(b);24             q.push(b);25         }26         if(a==2)27         {28             int ans=q.top();29             printf("%d\n",ans);30         }31         if(a==3)32         {33             q.pop();34         }35     }36     return 0;37 }
        
       
      
     

【模板】负环

1 #include
     
       2 using namespace std; 3 const int maxn=200005; 4  5 inline void read(int& x) 6 { 7    x=0; 8    register char f=getchar(),c=0; 9    while(!isdigit(f)&&f!='-')f=getchar();if(f=='-')c=1,f=getchar();10    while(isdigit(f))x=x*10+(f^48),f=getchar();if(c)x=~x+1;11 }12 13 struct node{14     int net;15     int to;16     int w;17 }a[maxn*3];18 int head[maxn];19 int dis[maxn],n,m,cnt,T;20 bool vis[maxn],flag;21 22 inline void add(int i,int j,int w)23 {24     a[++cnt].to=j;25     a[cnt].net=head[i];26     a[cnt].w=w;27     head[i]=cnt;28 }29 30 inline void spfa(int s)31 {32     if(flag)33         return ;34     vis[s]=true;35     for(int i=head[s];i;i=a[i].net)36     {37         if(flag)38             return ;39         int v=a[i].to;40         if(dis[v]>dis[s]+a[i].w)41         {42             dis[v]=dis[s]+a[i].w;43             if(vis[v])44             {45                 flag=true;46                 return ;47             }48             else49             {50                 spfa(v);51             }52         }53     }54     vis[s]=false;55 }56 57 int main()58 {59     read(T);60     while(T--)61     {62         memset(vis,false,sizeof vis);63         memset(dis,0,sizeof(dis));64         memset(head,0,sizeof(head));65         flag=false;66         cnt=0;67         read(n);68         read(m);69         for(int i=1;i<=m;i++)70         {71             int a,b,c;72             read(a);73             read(b);74             read(c);75             add(a,b,c);76             if(c>=0)77             {78                 add(b,a,c);79             }80         }81         for(int i=1;i<=n;i++)82         {83             spfa(i);84             if(flag)85                 break;86         }87         if(flag)88         {89             cout<<"YE5"<
     

【模板】可持久化线段树

1 #include
     
       2 using namespace std; 3 const int maxn=1000009;  4  5 struct node{ 6     int l; 7     int r; 8     int sum; 9 }t[maxn*20];10 int a[maxn],n,m;11 int tot;12 int rt[maxn];13 14 inline int read()15 {16     int x=0,f=1;17     char ch=getchar();18     while(ch<'0'||ch>'9')19     {20         if(ch=='-')f=-1;21         ch=getchar();22     }23     while(ch>='0'&&ch<='9')24     {25         x=x*10+ch-'0';26         ch=getchar();27     }28     return x*f;29 }30 31 void bt(int l,int r,int &x)32 {33     x=++tot;34     if(l==r)35     {36         t[x].sum=a[l];37         return ;38     }39     int mid=(l+r)>>1;40     bt(l,mid,t[x].l);41     bt(mid+1,r,t[x].r);42 }43 44 void update(int &x,int last,int l,int r,int pos,int sum)45 {46     x=++tot;47     t[x]=t[last];48     if(l==r)49     {50         t[x].sum=sum;51         return ;52     }53     int mid=(l+r)>>1;54     if(pos<=mid)55         update(t[x].l,t[last].l,l,mid,pos,sum);56     else57         update(t[x].r,t[last].r,mid+1,r,pos,sum);58 }59 60 inline int query(int x,int l,int r,int pos)61 {62     if(l==r)63         return t[x].sum;64     int mid=(l+r)>>1;65     if(pos<=mid)66         return query(t[x].l,l,mid,pos);67     else     68         return query(t[x].r,mid+1,r,pos);69 }70 71 int main()72 {73     n=read();74     m=read();75     for(register int i=1;i<=n;i++)76         a[i]=read();77     bt(1,n,rt[0]);78     for(register int i=1;i<=m;i++)79     {80         int v,o,p;81         v=read();82         o=read();83         p=read();84         if(o==1)85             update(rt[i],rt[v],1,n,p,read());86         else87         {88             printf("%d\n",query(rt[v],1,n,p));89             rt[i]=rt[v];90         }91     }92     return 0;93 }
     

【模板】线段树 1

1 #include
     
       2 using namespace std; 3 typedef long long  ll; 4 inline void read(ll& x) 5 { 6    x=0; 7    register char f=getchar(),c=0; 8    while(!isdigit(f)&&f!='-')f=getchar();if(f=='-')c=1,f=getchar(); 9    while(isdigit(f))x=x*10+(f^48),f=getchar();if(c)x=~x+1;10 }11 struct node12 {13   ll l,r,sum;    14 }t[300001];15 ll a[100001],lazy[300001];16 inline void bt(ll x,ll l,ll r)17 {18     t[x].l=l;19     t[x].r=r;20     if(l==r)21     {22         t[x].sum=a[l];23         return;24     }25     bt(x*2,l,(l+r)>>1);26     bt(x*2+1,1+((l+r)>>1),r);27     t[x].sum=t[x*2].sum+t[x*2+1].sum;28 }29 inline void pushdown(ll x)30 {31     ll mid=(t[x].l+t[x].r)/2;32     t[x*2].sum+=(mid-t[x].l+1)*lazy[x];33     t[x*2+1].sum+=(t[x].r-mid)*lazy[x];34     lazy[x*2]+=lazy[x];35     lazy[x*2+1]+=lazy[x];36     lazy[x]=0;37 }38 inline void update(ll x,ll l,ll r,ll k)39 {40     if(t[x].l>=l&&t[x].r<=r)41     {42         t[x].sum+=(t[x].r-t[x].l+1)*k;43         lazy[x]+=k;44         return;45     }46     if(t[x].r
      
       r)47         return ;48     if(lazy[x])49         pushdown(x);50     update(x<<1,l,r,k);51     update(x<<1|1,l,r,k);52     t[x].sum=t[x<<1|1].sum+t[x<<1].sum;53 }54 inline ll query(ll x,ll l,ll r)55 {56     if(t[x].l>=l&&t[x].r<=r)57     return t[x].sum;58     if(t[x].l>r||t[x].r
      
     

【模板】线段树 2

1 #include
     
        2 using namespace std;  3 typedef long long ll;  4 const int maxn=400000+5;  5 struct node{  6     ll jia,ch,r,l,s;  7 }t[maxn];  8 ll x,y,z,a[maxn],c,n,m,p,sum,k;  9  10 inline void bt(ll x,ll l,ll r) 11 { 12     t[x].l=l; 13     t[x].r=r; 14     t[x].jia=0; 15     t[x].ch=1; 16     if(l==r) 17     { 18         t[x].s=a[l]; 19         return ; 20     } 21     bt(x<<1,l,(r+l)>>1); 22     bt(x<<1|1,((r+l)>>1)+1,r); 23     t[x].s=(t[x<<1].s+t[x<<1|1].s)%p; 24 } 25  26 inline void down(ll x) 27 { 28     t[x*2].jia=(t[x*2].jia*t[x].ch+t[x].jia)%p; 29     t[x*2+1].jia=(t[x*2+1].jia*t[x].ch+t[x].jia)%p; 30     t[x*2].ch=(t[x*2].ch*t[x].ch)%p; 31     t[x*2+1].ch=(t[x*2+1].ch*t[x].ch)%p; 32     t[x*2].s=(t[x].jia*(t[x*2].r-t[x*2].l+1)%p+t[x*2].s*t[x].ch%p)%p; 33     t[x*2+1].s=(t[x].jia*(t[x*2+1].r-t[x*2+1].l+1)%p+t[x*2+1].s*t[x].ch%p)%p; 34     t[x].jia=0; 35     t[x].ch=1; 36 } 37  38 inline void cheng(ll x,ll d,ll l,ll r) 39 { 40     if(t[x].l>=l&&t[x].r<=r) 41     { 42         t[x].s=t[x].s*d%p; 43         t[x].jia=t[x].jia*d%p; 44         t[x].ch=t[x].ch*d%p; 45     } 46     else 47     { 48         down(x); 49         ll mid=(t[x].r+t[x].l)>>1; 50         if(mid>=l) 51             cheng(x<<1,d,l,r); 52         if(mid
      
       =l&&t[x].r<=r) 62     { 63         t[x].jia=(t[x].jia+d)%p; 64         t[x].s=((t[x].r-t[x].l+1)*d+t[x].s)%p; 65     } 66     else 67     { 68         down(x); 69         ll mid=(t[x].r+t[x].l)>>1; 70         if(mid>=l) 71             jf(x<<1,d,l,r); 72         if(mid
       
        =l) 82         return t[x].s%p; 83     else  84     { 85         down(x); 86         long long ans=0; 87         long long mid=(t[x].l+t[x].r)>>1; 88         if(mid>=l)ans=qh(l,r,x<<1)%p; 89         if(mid
        
         <<1|1); 90         return ans%p; 91     } 92 } 93  94 int main() 95 { 96     scanf("%lld%lld%lld",&n,&m,&p); 97     for(int i=1;i<=n;i++) 98     { 99         scanf("%lld",&a[i]);100     }101     bt(1,1,n);102     for(int i=1;i<=m;i++)103     {104         scanf("%lld",&c);105         if(c==1)106         {107             scanf("%lld%lld%lld",&x,&y,&k);108             cheng(1,k,x,y);109         }110         if(c==2)111         {112             scanf("%lld%lld%lld",&x,&y,&k);113             jf(1,k,x,y);114         }115         if(c==3)116         {117             scanf("%lld%lld",&x,&y);118             printf("%lld\n",qh(x,y,1));119         }120     }121     return 0;122 }
        
       
      
     

【模板】最近公共祖先（LCA）

1 #include
     
       2 using namespace std; 3  4 inline void read(int& x)  5 { 6    x=0; 7    register char f=getchar(),c=0; 8    while(!isdigit(f)&&f!='-') f=getchar(); 9    if(f=='-') c=1,f=getchar();10    while(isdigit(f)) x=x*10+(f^48),f=getchar();11    if(c) x=~x+1;12 }13 14 const int maxn=500000+5;15 struct node{16     int net;17     int to;18 }a[maxn*2];19 int n,m,s;20 int k=0;21 int head[maxn],d[maxn],p[maxn][21];22 int cnt;23 24 inline void add(int i,int j)25 {26     a[++cnt].to=j;27     a[cnt].net=head[i];28     head[i]=cnt;29 }30 31 inline void dfs(int u,int fa)32 {33     d[u]=d[fa]+1;34     p[u][0]=fa;35     for(register int i=1;(1<
      
       <=d[u];i++)36         p[u][i]=p[p[u][i-1]][i-1];37     for(register int i=head[u];i;i=a[i].net)38     {39         int v=a[i].to;40         if(v!=fa)41         {42             dfs(v,u);43         }44     }45 }46 47 inline int LCA(int a,int b)48 {49     if(d[a]>d[b])50         swap(a,b);51     for(register int i=20;i>=0;i--)52         if(d[a]<=d[b]-(1<
       
        =0;i--)57     {58         if(p[a][i]==p[b][i])59             continue;60         else61         {62             a=p[a][i];63             b=p[b][i];64         }    65     }66     return p[a][0];67 }68 69 int main()70 {71     read(n);72     read(m);73     read(s);74     for(register int i=1;i
       
      
     

【模板】最小生成树(kruskal)

1 #include
     
       2 using namespace std; 3 typedef long long ll; 4 const int maxn=200000; 5 struct node{ 6     ll u; 7     ll v; 8     ll w; 9 }a[maxn+5];10 ll fa[maxn+5];11 int n,m;12 ll ans,cnt;13 14 inline bool cmp(node a,node b)15 {16     return a.w
     

【模板】最小生成树(prim)邻接表

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define INF 0x7fffffff 5 const int maxn=500000+5; 6  7 using namespace std; 8  9 struct node{10     int to,nxt,w;11 }a[maxn];12 13 struct heapnode{14     int point,dist;15     bool operator > (const heapnode &o) const{16         return dist>o.dist;17     }18 };19 20 priority_queue
        
         
          ,greater
          
            >q;21 22 bool vis[maxn];23 int n,m,s,head[maxn],dis[maxn],tot,ans,cnt;24 25 void add(int u,int v,int w)26 {27 a[++tot].to=v;28 a[tot].w=w;29 a[tot].nxt=head[u];30 head[u]=tot;31 }32 33 int main()34 {35 memset(head,-1,sizeof(head));36 scanf("%d%d",&n,&m);37 s=1;38 for(int i=1;i<=m;++i)39 {40 int f,g,w;41 scanf("%d%d%d",&f,&g,&w);42 add(f,g,w);43 add(g,f,w);44 }45 fill(dis+1,dis+n+1,INF);46 dis[s]=0;47 vis[s]=true;48 for(int i=head[s];i!=-1;i=a[i].nxt)49 {50 q.push((heapnode){a[i].to,a[i].w});51 dis[a[i].to]=a[i].w;52 }53 while(!q.empty()&&cnt
           
            a[i].w)65 {66 dis[a[i].to]=a[i].w;67 q.push((heapnode){a[i].to,a[i].w});68 }69 }70 }71 if(n) 72 printf("%d\n",ans);73 else 74 printf("orz");75 return 0;76 }
           
          
         
        
       
      
     

【模板】最小生成树(prim)邻接矩阵

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
            //同上 8 using namespace std; 9 struct number{10 int x,i;11 bool operator < (const number &a) const {12 return x>a.x;//最小值优先，因为默认是大根堆的说。。。 13 }14 }A,B;//中转站而已 15 priority_queue 
            
              q;//堆 16 int map[5005][5005],n,m,a,b,c,ans;17 bool v[5005];18 int main()19 {20 memset(v,false,sizeof(v));21 memset(map,-1,sizeof(map));22 scanf("%d%d",&n,&m);23 for (int i=0;i
            
           
          
         
        
       
      
     

LCA【tarjan】

1 //LCA tarjan 2 #include
     
       3 using namespace std; 4 const int maxn = 1000; 5 int ask[maxn][maxn];//保存询问  6 int ans[maxn];//保存祖先i出现过的次数  7 int n,m; 8 vector
      
        g[maxn];//保存儿子  9 int root;//树的根 10 bool visit[maxn];11 bool isroot[maxn];12 int father[maxn];13 int Find(int x)14 {15     if(father[x] == x) 16         return x;17     else 18         return father[x] = Find(father[x]);19 }20 void init()21 {22     memset(ans,0,sizeof(ans));23     memset(visit,false,sizeof(visit));24     memset(isroot,true,sizeof(isroot));25     memset(ask,0,sizeof(ask));26     for(int i = 1; i <= n; i++)27     {28         g[i].clear();29         father[i] = i;30     }31 32 }33 void LCA(int root)34 {35     for(int i = 1; i <= n; i++)36     {37         if(visit[i]&&ask[root][i])38         {39             ans[Find(i)] += ask[root][i];40         }41     }42     visit[root] = true;43     for(int i = 0; i < g[root].size(); i++)44     {45         int term = g[root][i];46         LCA(term);47         father[term] = root;48     }49 }50 int main()51 {52     while(~scanf("%d",&n))53     {54         init();55         int f,s,num;56         for(int i = 1; i <= n; i++)57         {58             scanf("%d:(%d)",&f,&num);59             for(int j = 1; j <= num; j++)60             {61                 scanf(" %d",&s);62                 isroot[s] = false;63                 g[f].push_back(s);64             }65         }66         for(int i = 1; i <= n; i++)67         {68             if(isroot[i])69             {70                 root = i;71                 break;72             }73         }74         scanf("%d",&m);75         int u,v;76         for(int i = 1; i <= m; i++)77         {78             scanf(" (%d %d)",&u,&v);79             ask[u][v]++;80             ask[v][u]++;81         }82         LCA(root);83         for(int i = 1; i <= n; i++)84         {85             if(ans[i])86             {87                 printf("%d:%d\n",i,ans[i]);88             }89         }90     }91     return 0;92 }
      
     

LCA【倍增法】

1 #include
     
       2 using namespace std; 3  4 inline void read(int& x) 5 { 6    x=0; 7    register char f=getchar(),c=0; 8    while(!isdigit(f)&&f!='-') 9    f=getchar();10    if(f=='-')11    c=1,f=getchar();12    while(isdigit(f))13    x=x*10+(f^48),f=getchar();14    if(c)15    x=~x+1;16 }17 18 const int maxn=500000+5;19 struct node{20     int net;21     int to;22 }a[maxn*2];23 int n,m,s,cnt;24 int head[maxn*2],dep[maxn*2],bz[maxn][22];25 26 inline void add(int i,int j)27 {28     a[++cnt].to=j;29     a[cnt].net=head[i];30     head[i]=cnt;31 }32 33 inline void dfs(int u,int fa)34 {35     dep[u]=dep[fa]+1;36     bz[u][0]=fa;37     for(register int i=1;(1<
      
       <=dep[u];i++)38         bz[u][i]=bz[bz[u][i-1]][i-1];39     for(register int i=head[u];i;i=a[i].net)40     {41         int v=a[i].to;42         if(v!=fa)43         {44             dfs(v,u);45         }46     }47 }48 49 inline int lca(int a,int b)50 {51     if(dep[a]>dep[b])52         swap(a,b);53     for(register int i=20;i>=0;i=~(-i))54         if(dep[a]<=dep[b]-(1<
       
        =0;i=~(-i))61     {62         if(bz[a][i]==bz[b][i])63             continue;64         else65         {66             a=bz[a][i];67             b=bz[b][i];68         }69     }70     return bz[a][0];71 }72 73 int main()74 {75     read(n);76     read(m);77     read(s);78     for(register int i=1;i
       
      
     

LCA【树剖法】

1 //LCA树剖法 2 #include
     
       3 using namespace std; 4 struct node 5 { 6     int y,next; 7 }e[201000]; 8 int n,m,len,z,head[201000]; 9 int dep[201000];//用来保存当前节点的深度 10 int f[201000];//保存当前节点的父亲 11 int top[201000];//保存当前节点的所在链的顶端节点 12 int son[201000];//保存重儿子 13 int size[201000];//用来保存以x为根的子树节点个数 14 15 inline int read()16 {17     int x=0,f=1;  char ch=getchar();18     while(!isdigit(ch))  {
   if(ch=='-')  f=-1;  ch=getchar();}19     while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}20     return x*f;21 }22 23 void insert(int xx,int yy)24 {25     e[++len].next=head[xx];26     head[xx]=len;27     e[len].y=yy;28 }29 30 void dfs1(int x)31 {32     dep[x]=dep[f[x]]+1;33     size[x]=1;34     for(int i=head[x];i;i=e[i].next)35     {36         if(e[i].y!=f[x]&&!f[e[i].y])37         {38             f[e[i].y]=x;39             dfs1(e[i].y);40             size[x]+=size[e[i].y];41             if(size[son[x]]
      
       dep[top[yy]])63             xx=f[top[xx]];64         else65             yy=f[top[yy]];66     }67     if(dep[xx]
      
     

快速幂

1 #include
     
       2 using namespace std; 3 typedef long long ll; 4 ll b,p,k; 5 inline ll qpow(ll a,ll b) 6 { 7     ll ans=1; 8     while(b) 9     {10         if(b&1)11             ans=(ans*a)%k;12         b=b>>1;13         a=(a*a)%k;14     }15     return ans;16 }17 int main()18 {19     cin>>b>>p>>k;20     cout<
      <<"^"<
<<" "<<"mod "<
        
         <<"="<
        
     

求树上两点距离（边权为1时）

1 #include
     
       2 using namespace std; 3 int n; 4 int deep[100005]; 5 int ru[100005]; 6 int fa[100005]; 7 int head[100005],cnt; 8 struct node { 9     int v,next;10 } e[200005];11 inline void add(int u,int v) {12     e[++cnt].next=head[u];13     e[cnt].v=v;14     head[u]=cnt;15 }16 inline void Deep_pre(int x,int dep) {17     deep[x]=dep;18     for(register int i=head[x]; i; i=e[i].next) {19         if(e[i].v==fa[x]) continue;20         fa[e[i].v]=x;21         Deep_pre(e[i].v,dep+1);22     }23 }24 inline int lca(int x,int y) {25     if(deep[x]>deep[y])swap(x,y);26     while(deep[x]!=deep[y]) {27         y=fa[y];28     }29     while(x!=y) {30         x=fa[x];31         y=fa[y];32     }33     return x;34 }35 int main() {36     scanf("%d",&n);37     for(register int i=1,u,v; i
     

 平衡树-splay

1 #include
     
        2 using namespace std;  3   4 const int maxn=110000;  5   6 struct node{  7     int d,n,c,f,son[2];//d为值,f为父亲的编号,c为控制的节点数,n为同值的节点个数   8 }t[maxn*5];  9 int len,root; 10  11 inline void update(int x)//更新x所控制的节点数  12 { 13     int lc=t[x].son[0],rc=t[x].son[1]; 14     t[x].c=t[lc].c+t[rc].c+t[x].n; 15 } 16  17 inline void add(int d,int f)//添加值为d的点,认f为父亲,同时,f也认它为孩子  18 { 19     len++; 20     t[len].d=d; 21     t[len].n=1; 22     t[len].c=1; 23     t[len].f=f; 24     if(d
      
       准备当新儿子  38     t[R].son[1-w]=r; 39     if(r!=0) 40         t[r].f=R; 41      42     r=x;R=ff;//x->准备当新儿子  43     if(t[R].son[0]==f) 44         t[R].son[0]=r; 45     else      46         t[R].son[1]=r; 47     t[r].f=R; 48      49     r=f;R=x;//x的父亲->准备当新儿子  50     t[R].son[w]=r; 51     t[r].f=R; 52      53     update(f);//先更新处于下层的点f  54     update(x);//再更新上层的x  55 } 56  57 inline void splay(int x,int rt)//该函数功能是为了让x变成rt的孩子(左右都可以)  58 { 59     while(t[x].f!=rt)//如果x的爷爷是rt,那么x只需要旋转一次(相当于跳一层)  60     { 61         int f=t[x].f,ff=t[f].f; 62         if(ff==rt) 63         { 64             if(t[f].son[0]==x) 65                 rotate(x,1); 66             else 67                 rotate(x,0); 68         } 69         else 70         { 71             if(t[ff].son[0]==f&&t[f].son[0]==x) 72             { 73                 rotate(f,1);rotate(x,1); 74             } 75             else if(t[ff].son[1]==f&&t[f].son[1]==x) 76             { 77                 rotate(f,0);rotate(x,0); 78             } 79             else if(t[ff].son[0]==f&&t[f].son[1]==x) 80             { 81                 rotate(x,0);rotate(x,1); 82             } 83             else if(t[ff].son[1]==f&&t[f].son[0]==x) 84             { 85                 rotate(x,1);rotate(x,0); 86             } 87         } 88     } 89     if(rt==0) 90         root=x; 91 } 92  93 inline int findip(int d)//找值为d的节点地址,补充:如果不存在d,有可能是接近d的(或大或小) 94 { 95     int x=root; 96     while(t[x].d!=d) 97     { 98         if(d
       
        1)//多重身份,就不用删点 144     {145         t[x].n--;146         update(x);147         return ;148     }149     if(t[x].son[0]==0&&t[x].son[1]==0)150     {151         root=0;152         len=0;153     }154     else if(t[x].son[0]==0&&t[x].son[1]!=0)155     {156         root=t[x].son[1];157         t[root].f=0;158     }159     else if(t[x].son[0]!=0&&t[x].son[1]==0)160     {161         root=t[x].son[0];162         t[root].f=0;163     }164     else165     {166         int p=t[x].son[0];167         while(t[p].son[1]!=0)168             p=t[p].son[1];169         splay(p,x);170         171         int r=t[x].son[1],R=p;172         173         t[R].son[1]=r;174         t[r].f=R;175         176         root=R;177         t[root].f=0;178         update(R);179     }180 }181 182 inline int findrank(int d)//找排名 183 {184     int x=findip(d);185     splay(x,0);186     return t[t[x].son[0]].c+1;187 }188 189 inline int findshuzhi(int k)//找排名为k的值 190 {191     int x=root;192     while(true)193     {194         int lc=t[x].son[0],rc=t[x].son[1];195         if(k<=t[lc].c) 196             x=lc;//去左孩子查找 197         else if(k>t[lc].c+t[x].n)198         {199             k-=t[lc].c+t[x].n;200             x=rc;201         }//去右孩子查找 202         else 203             break;//就是你 204     }205     splay(x,0);206     return t[x].d;207 }208 209 inline int findqianqu(int d)//找前驱 210 {211     int x=findip(d);212     splay(x,0);213     if(d<=t[x].d&&t[x].son[0]!=0) 214     {215         x=t[x].son[0];216         while(t[x].son[1]!=0)217             x=t[x].son[1];218     }219     if(t[x].d>=d)//如果是if(t[x].d>d)则找到的是:小于等于d的前驱 220         x=0;221         return t[x].d;222 }223 224 inline int findhouji(int d)//找后继 225 {226     int x=findip(d);227     splay(x,0);228     if(t[x].d<=d&&t[x].son[1]!=0)229     {230         x=t[x].son[1];231         while(t[x].son[0]!=0)232             x=t[x].son[0];233     }234     if(t[x].d<=d)235         x=0;236     return t[x].d;237 }238 239 int main()240 {241     int n,opt,x;242     scanf("%d",&n);243     for(int i=1;i<=n;i++)244     {245         scanf("%d%d",&opt,&x);246         if(opt==1)247         {248             insert(x);249         }250         if(opt==2)251         {252             del(x);253         }254         if(opt==3)255         {256             printf("%d\n",findrank(x));257         }258         if(opt==4)259         {260             printf("%d\n",findshuzhi(x));261         }262         if(opt==5)263         {264             printf("%d\n",findqianqu(x));265         }266         if(opt==6)267         {268             printf("%d\n",findhouji(x));269         }270     }271     return 0;272 }
       
      
     

 分块

1 #include
     
       2 using namespace std; 3 typedef long long ll; 4 const int maxn=1e5+7; 5  6 int block,belong[maxn],num,l[maxn],r[maxn],n,q; 7 ll a[maxn],Max[maxn]; 8  9 inline void bt()10 {11     block=sqrt(n);12     num=n/block;13     if(n%block)14         num++;15     for(int i=1;i<=num;i++)16         l[i]=(i-1)*block+1,r[i]=i*block;17     r[num]=n;18     for(int i=1;i<=n;i++)19         belong[i]=(i-1)/block+1;20     for(int i=1;i<=num;i++)21     {22         for(int j=l[i];j<=r[i];j++)23             Max[i]=max(Max[i],a[j]);24     }25 }26 27 inline void update(int x,int y)28 {29     a[x]+=y;30     Max[belong[x]]=max(Max[belong[x]],a[x]);31 }32 33 inline ll ask(int x,int y)34 {35     ll ans=0;36     if(belong[x]==belong[y])37     {38         for(int i=x;i<=y;i++)39             ans=max(a[i],ans);40         return ans;41     }42     for(int i=x;i<=r[belong[x]];i++)43     {44         ans=max(ans,a[i]);45     }46     for(int i=belong[x]+1;i
     

文艺平衡树（翻转区间）

1 #include
     
        2 using namespace std;  3   4 const int maxn=110000;  5   6 struct node{  7     int d,c,n,f,son[2];  8     bool fz;  9     node(){fz=false;} 10 }t[maxn]; 11 int len,root; 12 void add(int d,int f) 13 { 14     len++; 15     t[len].d=d;t[len].f=f; 16     t[len].n=t[len].c=1; 17     t[len].son[0]=t[len].son[1]=0; 18     if(d
      
       t[lc].c+t[x].n)164         {165             k-=t[lc].c+t[x].n;166             x=rc;167         }168         else169             break;170     }171     splay(x,0);172     return x;173 }174 175 inline void fz(int x,int y)176 {177     int lc=findrank(x-1),rc=findrank(y+1);178     splay(lc,0);179     splay(rc,lc);180     int p=t[rc].son[0];181     t[p].fz=1-t[p].fz;182     splay(p,0);183 }184 185 int n,m;186 int a[maxn],llen;187 188 void dfs(int x)189 {190     if(t[x].fz==true)    191         whfz(x);192     int lc=t[x].son[0],rc=t[x].son[1];193     if(lc==0&&rc==0)194     {195         a[++llen]=t[x].d;196         return ;197     }198     if(lc!=0)199         dfs(lc);200     a[++llen]=t[x].d;201     if(rc!=0)202         dfs(rc);203 }204 205 int main()206 {207     scanf("%d%d",&n,&m);208     len=0,root=0;209     for(int i=1;i<=n;i++)210         insert(i);211     insert(n+1);insert(n+2);212     for(int i=1;i<=m;i++)213     {214         int x,y;215         scanf("%d%d",&x,&y);216         x++;217         y++;218         fz(x,y);219     }220     llen=0;221     dfs(root);222     for(int i=2;i
      
     

 主席树（求静态区间第K小）

1 #include
     
       2 using namespace std; 3 const int maxn=210000; 4 int n,m,cnt; 5 struct node 6 { 7     int l; 8     int r; 9     int sum;10 } t[maxn*60];11 int rk[maxn],rt[maxn];12 struct p13 {14     int x;15     int pp;16     bool operator < (const p &_) const17     {18         return x<_.x;19     }20 } a[maxn];21 22 inline void bt(int &num,int &x,int l,int r)23 {24     t[cnt++]=t[x];25     x=cnt-1;26     ++t[x].sum;27     if(l==r)28         return ;29     int mid=(l+r)>>1;30     if(num<=mid)31         bt(num,t[x].l,l,mid);32     else33         bt(num,t[x].r,mid+1,r);34 35 }36 37 inline int query(int i,int j,int k,int l,int r)38 {39     if(l==r)40         return l;41     int tt=t[t[j].l].sum-t[t[i].l].sum;42     int mid=(l+r)>>1;43     if(k<=tt)44         return query(t[i].l,t[j].l,k,l,mid);45     else46         return query(t[i].r,t[j].r,k-tt,mid+1,r);47 }48 49 int main()50 {51     t[0].l=t[0].r=t[0].sum;52     rt[0]=0;53     scanf("%d%d",&n,&m);54     for(int i=1; i<=n; i++)55     {56         scanf("%d",&a[i].x);57         a[i].pp=i;58     }59     sort(a+1,a+1+n);60     for(int i=1; i<=n; i++)61         rk[a[i].pp]=i;62     cnt=1;63     for(int i=1; i<=n; i++)64     {65         rt[i]=rt[i-1];66         bt(rk[i],rt[i],1,n);67     }68     while(m--)69     {70         int i,j,k;71         scanf("%d%d%d",&i,&j,&k);72         printf("%d\n",a[query(rt[i-1],rt[j],k,1,n)].x);73     }74     return 0;75 }