模板大集合

【模板】KMP字符串匹配

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<string>
 6 #include<cmath>
 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<len2;i++)//自己匹配自己
18     {
19         while(k&&a2[i]!=a2[k])    
20             k=kmp[k];//找到最长的前后缀重叠长度
21         kmp[i+1]=a2[i]==a2[k]?++k:0;//不相等的情况，即无前缀能与后缀重叠，直接赋值位0（注意是给下一位，因为匹配的是下一位适失配的情况）
22     }
23     k=0;
24     for(int i=0;i<len1;i++)
25     {
26         while(k&&a1[i]!=a2[k])
27             k=kmp[k];//如果不匹配，则将利用kmp数组往回跳
28         k+=a1[i]==a2[k]?1:0;//如果相等了，则匹配下一位
29         if(k==len2)
30             printf("%d
",i-len2+2);//如果已经全部匹配完毕，则输出初始位置
31     }
32     for(int i=1;i<=len2;i++)
33         printf("%d ",kmp[i]);//输出f数组
34     return 0;
35 }

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

 1 #include<bits/stdc++.h>
 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<l)
46         return 0;
47     return max(query(x<<1,r,l),query(x<<1|1,r,l));
48 }
49 
50 int main()
51 {
52     read(n);
53     read(m);
54     for(int i=1;i<=n;i++)
55         read(a[i]);
56     bt(1,1,n);
57     for(int i=1;i<=m;i++)
58     {
59         int l,r;
60         read(l);
61         read(r);
62         printf("%d
",query(1,r,l));
63     }
64     return 0;
65 }

【模板】并查集

 1 #include<bits/stdc++.h>
 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"<<endl;
42                 else
43                     cout<<"N"<<endl;
44                 break;
45             }        
46         }    
47     }
48     return 0;
49 }

【模板】堆

 1 #include<bits/stdc++.h>
 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<int,vector<int>,greater<int> > 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
",ans);
30         }
31         if(a==3)
32         {
33             q.pop();
34         }
35     }
36     return 0;
37 }

【模板】负环

 1 #include<bits/stdc++.h>
 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             else
49             {
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"<<endl;
90         }
91         else
92         {
93             cout<<"N0"<<endl;
94         }
95     }
96     return 0;
97 }

【模板】可持久化线段树

 1 #include<bits/stdc++.h>
 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     else
57         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         else
87         {
88             printf("%d
",query(rt[v],1,n,p));
89             rt[i]=rt[v];
90         }
91     }
92     return 0;
93 }

【模板】线段树 1

 1 #include<bits/stdc++.h>
 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 node
12 {
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<l||t[x].l>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<l)
59     return 0;
60     if(lazy[x])
61         pushdown(x);
62     return query(x<<1,l,r)+query(x<<1|1,l,r);
63 } 
64 int main()
65 {
66     ll n,m,x,y,z,t;
67     read(n);
68     read(m);
69     for(ll i=1;i<=n;i++)
70         read(a[i]);
71     bt(1,1,n);
72     for(ll  i=1;i<=m;i++) 
73     {
74         read(t);
75         read(x);
76         read(y);
77         if(t==1)
78         {
79             read(z);
80             update(1,x,y,z);
81         }
82         else 
83             printf("%lld
",query(1,x,y));
84     }
85     return 0;
86 }

【模板】线段树 2

  1 #include<bits/stdc++.h>
  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<r)
 53             cheng(x<<1|1,d,l,r);
 54         t[x].s=(t[x<<1].s+t[x<<1|1].s)%p;    
 55     }
 56     return ;
 57 }
 58 
 59 inline void jf(ll x,ll d,ll l,ll r)
 60 {
 61     if(t[x].l>=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<r)
 73             jf(x<<1|1,d,l,r);
 74         t[x].s=(t[x<<1].s+t[x<<1|1].s)%p;
 75     }
 76     return ;
 77 }
 78 
 79 long long qh(long long l,long long r,long long x)
 80 {
 81     if(t[x].r<=r&&t[x].l>=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<r)ans=ans+qh(l,r,x<<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
",qh(x,y,1));
119         }
120     }
121     return 0;
122 }

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

 1 #include<bits/stdc++.h>
 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<<i)<=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<<i))
53             b=p[b][i];
54     if(a==b)
55         return a;
56     for(register int i=20;i>=0;i--)
57     {
58         if(p[a][i]==p[b][i])
59             continue;
60         else
61         {
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<n;i++)
75     {
76         int a,b;
77         read(a);
78         read(b);
79         add(a,b);
80         add(b,a);
81     }
82     dfs(s,0);
83     for(register int i=1;i<=m;i++)
84     {
85         int a,b;
86         read(a);
87         read(b);
88         printf("%d
",LCA(a,b));
89     }
90     return 0;
91 }

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

 1 #include<bits/stdc++.h>
 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<b.w;
17 }
18 
19 inline ll find(ll x)
20 {
21     if(fa[x]!=x)
22         fa[x]=find(fa[x]);
23     return fa[x];
24 }
25 
26 inline void kruskal()
27 {
28     sort(a,a+m,cmp);
29     for(int i=0;i<m;i++)
30     {
31         ll u=a[i].u;
32         ll v=a[i].v;
33         ll w=a[i].w;
34         ll f=find(u);
35         ll ff=find(v);
36         if(f==ff)
37             continue;
38         ans+=w;
39         fa[ff]=f;
40         cnt++;
41         if(cnt==n-1)
42             break;
43     }
44 }
45 
46 int main()
47 {
48     scanf("%d%d",&n,&m);
49     for(int i=1;i<=n;i++)
50         fa[i]=i;
51     for(int i=0;i<m;i++)
52     {
53         scanf("%lld%lld%lld",&a[i].u,&a[i].v,&a[i].w);
54     }
55     kruskal();
56     if(cnt!=n-1)
57         printf("orz");
58     printf("%lld
",ans);
59     return 0;
60 }

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

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 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<heapnode,vector<heapnode>,greater<heapnode> >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<n)
54     {
55         heapnode now=q.top();
56         q.pop();
57         if(vis[now.point])  
58             continue;
59         ++cnt;
60         ans+=now.dist;
61         vis[now.point]=true;
62         for(int i=head[now.point];i;i=a[i].nxt)
63         {
64             if(dis[a[i].to]>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
",ans);
73     else 
74         printf("orz");
75     return 0;
76 }

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <queue>//同上 
 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 <number> 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<m;i++)
24     {
25         scanf("%d%d%d",&a,&b,&c);
26         if (map[a][b]==-1||c<map[a][b]) 
27             map[a][b]=c;
28         if (map[b][a]==-1||c<map[b][a]) 
29             map[b][a]=c;
30     }
31     v[1]=true;
32     for (int i=1;i<=n;i++)
33         if (map[1][i]!=-1)
34         {
35             A.x=map[1][i];
36             A.i=i;
37             q.push(A);
38         }
39     for (int i=1;i<n;i++)
40     {
41         if (q.empty())
42         {
43             printf("orz");
44             return 0;
45         }
46         B=q.top();
47         q.pop();
48         while (v[B.i])
49         {
50             B=q.top();
51             q.pop();
52             if (q.empty())
53             {
54                 printf("orz");
55                 return 0;
56             }
57         }
58         ans+=B.x;
59         v[B.i]=true;
60         for (int j=1;j<=n;j++)
61         if (map[B.i][j]!=-1&&!v[j])
62         {
63             A.x=map[B.i][j];
64             A.i=j;
65             q.push(A);
66         }
67     }
68     printf("%d
",ans);
69     return 0;
70 }

LCA【tarjan】

 1 //LCA tarjan
 2 #include<bits/stdc++.h>
 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<int> 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
",i,ans[i]);
88             }
89         }
90     }
91     return 0;
92 }

LCA【倍增法】

 1 #include<bits/stdc++.h>
 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<<i)<=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<<i))
55         {
56             b=bz[b][i];
57         }
58     if(a==b)
59         return a;
60     for(register int i=20;i>=0;i=~(-i))
61     {
62         if(bz[a][i]==bz[b][i])
63             continue;
64         else
65         {
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<n;i=-(~i))
79     {
80         int a,b;
81         read(a);
82         read(b);
83         add(a,b);
84         add(b,a);
85     }
86     dfs(s,0);
87     for(register int i=1;i<=m;i=-(~i))
88     {
89         int a,b;
90         read(a);
91         read(b);
92         printf("%d
",lca(a,b));
93     }
94     return 0;
95 }

LCA【树剖法】

 1 //LCA树剖法
 2 #include<bits/stdc++.h>
 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]]<size[e[i].y])
42                 son[x]=e[i].y;
43         }
44     }
45 }
46 
47 void dfs2(int x)
48 {
49     if(x==son[f[x]])
50         top[x]=top[f[x]];
51     else
52         top[x]=x;
53     for(int i=head[x];i;i=e[i].next)
54         if(f[e[i].y]==x)
55             dfs2(e[i].y);
56 }
57 
58 int LCA(int xx,int yy)
59 {
60     while(top[xx]!=top[yy])
61     {
62         if(dep[top[xx]]>dep[top[yy]])
63             xx=f[top[xx]];
64         else
65             yy=f[top[yy]];
66     }
67     if(dep[xx]<dep[yy])
68         return xx;
69     else 
70         return yy;
71 }
72 
73 int main()
74 {
75     n=read();
76     m=read();
77     for(int i=1;i<n;i++)
78     {
79         int xx=read();
80         int yy=read();
81         insert(xx,yy);
82         insert(yy,xx);
83     }
84     dfs1(1);
85     dfs2(1);
86     for(int i=1;i<=m;i++)
87     {
88         int xx=read(),yy=read();
89         printf("%d
",LCA(xx,yy));
90     }
91     return 0;
92 }

快速幂

 1 #include<bits/stdc++.h>
 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<<b<<"^"<<p<<" "<<"mod "<<k<<"="<<qpow(b,p);
21     return 0;
22 }

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

 1 #include<bits/stdc++.h>
 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<n; ++i) {
38         scanf("%d%d",&u,&v);
39         add(u,v);
40         add(v,u);
41     }
42     int root=1;
43     fa[root]=0;
44     Deep_pre(root,1);
45     int m,ui,vi;
46     scanf("%d",&m);
47     for(register int i=1; i<=m; ++i) {
48         scanf("%d%d",&ui,&vi);
49         int LCA=lca(ui,vi);
50         printf("%d
",deep[ui]+deep[vi]-2*deep[LCA]);
51     }
52     return 0;
53 }
54 /*
55 5
56 1 3
57 2 4
58 3 5
59 2 3
60 10
61 1 3
62 2 4
63 5 3
64 5 1
65 4 2
66 1 5
67 1 4
68 1 3
69 2 4
70 2 1
71 */

平衡树-splay

  1 #include<bits/stdc++.h>
  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<t[f].d)
 25         t[f].son[0]=len;
 26     else
 27         t[f].son[1]=len;
 28     t[len].son[0]=t[len].son[1]=0;
 29 }
 30 
 31 inline void rotate(int x,int w)//左旋(x,0)或者右旋(x,1) 
 32 {
 33     int f=t[x].f,ff=t[f].f;//x在旋转之前,要确定x的父亲f和爷爷ff
 34     //下来建立关系 
 35     int r,R;//r代表儿辈,R表示父辈 
 36     //有4个角色:我x,我的儿子,我的父亲,我的爷爷 
 37     r=t[x].son[w];R=f;//x的儿子->准备当新儿子 
 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<t[x].d)
 99         {
100             if(t[x].son[0]==0)
101                 break;
102             else
103                 x=t[x].son[0];
104         }
105         else
106         {
107             if(t[x].son[1]==0)
108                 break;
109             else
110                 x=t[x].son[1];
111         }
112     }
113     return x;
114 }
115 
116 inline void insert(int d)//插入数值为d的一个节点 
117 {
118     if(root==0)
119     {
120         add(d,0);
121         root=len;
122         return ;
123     }
124     int x=findip(d);
125     if(t[x].d==d)
126     {
127         t[x].n++;
128         update(x);
129         splay(x,0);
130     }
131     else
132     {
133         add(d,x);
134         update(x);
135         splay(len,0);
136     }
137 }
138 
139 inline void del(int d)//删除数值为d的一个节点 
140 {
141     int x=findip(d);
142     splay(x,0);//找人,并且让y当树根 
143     if(t[x].n>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     else
165     {
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
",findrank(x));
257         }
258         if(opt==4)
259         {
260             printf("%d
",findshuzhi(x));
261         }
262         if(opt==5)
263         {
264             printf("%d
",findqianqu(x));
265         }
266         if(opt==6)
267         {
268             printf("%d
",findhouji(x));
269         }
270     }
271     return 0;
272 }

分块

 1 #include<bits/stdc++.h>
 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<belong[y];i++)
47     {
48         ans=max(ans,Max[i]);
49     }
50     for(int i=belong[y];i<=y;i++)
51     {
52         ans=max(ans,a[i]);
53     }
54     return ans;
55 }
56 
57 int main()
58 {
59     scanf("%d%d",&n,&q);
60     bt();
61     for(int i=1;i<=q;i++)
62     {
63         int op,l,r;
64         scanf("%d%d%d",&op,&l,&r);
65         if(op==1)
66             update(l,r);
67         else 
68             printf("%lld
",ask(l,r));
69     }
70     return 0;
71 }

文艺平衡树（翻转区间）

  1 #include<bits/stdc++.h>
  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[f].d)
 19         t[f].son[0]=len;
 20     else
 21         t[f].son[1]=len;
 22 }
 23 
 24 inline void update(int x)
 25 {
 26     int lc=t[x].son[0],rc=t[x].son[1];
 27     t[x].c=t[lc].c+t[rc].c+t[x].n;
 28 }
 29 
 30 inline void whfz(int x)
 31 {
 32     t[x].fz=false;
 33     int lc=t[x].son[0],rc=t[x].son[1];
 34     swap(t[x].son[0],t[x].son[1]);
 35     t[lc].fz=1-t[lc].fz;
 36     t[rc].fz=1-t[rc].fz;
 37 }
 38 
 39 inline int findip(int d)
 40 {
 41     int x=root;
 42     while(t[x].d!=d)
 43     {
 44         if(d<t[x].d)    
 45         {
 46             if(t[x].son[0]==0)
 47                 break;
 48             x=t[x].son[0];
 49         }
 50         else
 51         {
 52             if(t[x].son[1]==0)
 53                 break;
 54             x=t[x].son[1];
 55         }
 56     }
 57     return x;
 58 }
 59 
 60 inline void rotate(int x,int w)
 61 {
 62     int f=t[x].f,ff=t[f].f;
 63     int r,R;
 64     
 65     r=t[x].son[w],R=f;
 66     t[R].son[1-w]=r;
 67     if(r!=0)
 68         t[r].f=R;
 69         
 70     r=x,R=ff;
 71     if(t[R].son[0]==f)
 72         t[R].son[0]=r;
 73     else
 74         t[R].son[1]=r;
 75     t[r].f=ff;
 76     
 77     r=f,R=x;
 78     t[R].son[w]=r;
 79     t[r].f=R;
 80     
 81     update(f);
 82     update(x);
 83 }
 84 
 85 inline void splay(int x,int rt)
 86 {
 87     while(t[x].f!=rt)
 88     {
 89         int f=t[x].f,ff=t[f].f;
 90         if(ff==rt)
 91         {
 92             if(t[x].fz==true)
 93                 whfz(f);
 94             if(t[f].son[0]==x)
 95                 rotate(x,1);
 96             else
 97                 rotate(x,0);
 98         }
 99         else
100         {
101             if(t[x].fz==true)
102                 whfz(x);
103             if(t[f].fz==true)
104             {
105                 t[f].fz=false;
106                 t[x].fz=true;
107             }
108             if(t[f].son[0]==x&&t[ff].son[0]==f)
109             {
110                 rotate(f,1);rotate(x,1);
111             }
112             else if(t[f].son[1]==x&&t[ff].son[1]==f)
113             {
114                 rotate(f,0);rotate(x,0);
115             }
116             else if(t[f].son[0]==x&&t[ff].son[1]==f)
117             {
118                 rotate(x,1);rotate(x,0);
119             }
120             else if(t[f].son[1]==x&&t[ff].son[0]==f)
121             {
122                 rotate(x,0);rotate(x,1);
123             }
124         }
125     }
126     if(rt==0)
127         root=x;
128 }
129 
130 inline void insert(int d)
131 {
132     if(root==0)
133     {
134         add(d,0);
135         root=len;
136         return ;
137     }
138     int x=findip(d);
139     if(t[x].d==d)
140     {
141         t[x].n++;
142         update(d);
143         splay(x,0);
144     }
145     else
146     {
147         add(d,x);
148         update(x);
149         splay(len,0);
150     }
151 }
152 
153 inline int findrank(int k)
154 {
155     int x=root;
156     while(true)
157     {
158         if(t[x].fz==true)
159             whfz(x);
160         int lc=t[x].son[0],rc=t[x].son[1];
161         if(k<=t[lc].c)
162             x=lc;
163         else if(k>t[lc].c+t[x].n)
164         {
165             k-=t[lc].c+t[x].n;
166             x=rc;
167         }
168         else
169             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<llen-1;i++)
223         printf("%d ",a[i]-1);
224     printf("%d
",a[llen-1]-1);
225     return 0;
226 }

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

 1 #include<bits/stdc++.h>
 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 p
13 {
14     int x;
15     int pp;
16     bool operator < (const p &_) const
17     {
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     else
33         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     else
46         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
",a[query(rt[i-1],rt[j],k,1,n)].x);
73     }
74     return 0;
75 }