模板大集合
2018-06-27 10:05:37来源:未知 阅读 ()
【模板】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\n",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\n",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\n",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\n",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\n",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\n",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\n",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\n",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\n",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\n",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\n",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\n",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\n",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\n",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\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<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\n",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\n",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\n",a[query(rt[i-1],rt[j],k,1,n)].x); 73 } 74 return 0; 75 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 单调队列模板【附例题】 2020-05-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash