模版题目的集合
一大波模版题正在来袭
难度不一定递增，但应该是大致递增的难度。
【模板】快速读入
#include<bits/stdc++.h>
using namespace std;
int sum;
int in(){int k=0,f=1;char c=getchar_unlocked();while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar_unlocked();}while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar_unlocked();return k*f;
}
void out(int x){if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else out(x/10),putchar(x%10+'0');
}
signed main(){int n=in();while(n--)sum+=in();out(sum);
}
【模板】栈
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n;
int T;
signed main(){ios::sync_with_stdio(0);cin>>T;while(T--){cin>>n;stack<int>t;while(n--){string s;cin>>s;if(s=="push"){int x;cin>>x;t.push(x);}else if(s=="query"){if(t.empty())cout<<"Anguei!\n";else cout<<t.top()<<'\n';}else if(s=="pop"){if(t.empty())cout<<"Empty\n";else t.pop();}else cout<<t.size()<<'\n';}}
}
【模板】快速幂
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,p;
int T;
signed main(){ios::sync_with_stdio(0);cin>>a>>b>>p;int k=b;int kk=a;int ans=1;while(b){if(b&1)ans=(ans*a)%p;a=(a*a)%p;b>>=1;}cout<<kk<<'^'<<k<<" mod "<<p<<'='<<ans;
}
【模板】队列
#include<bits/stdc++.h>
using namespace std;
int n;
int T;
queue<int>q;
signed main(){ios::sync_with_stdio(0);cin>>T;while(T--){int op;cin>>op;if(op==1){int x;cin>>x;q.push(x);}else if(op==2){if(q.empty())cout<<"ERR_CANNOT_POP\n";else q.pop();}else if(op==3){if(q.empty())cout<<"ERR_CANNOT_QUERY\n";else cout<<q.front()<<'\n';}else{cout<<q.size()<<'\n';}}
}
【模板】排序
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n;
int a[N];
signed main(){ios::sync_with_stdio(0);cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);for(int i=1;i<=n;i++)cout<<a[i]<<' ';
}
【模板】Floyd
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=5e3+5;
const int INF=1e9+5;
int a[M][M];
int n,m;
int T;
signed main(){ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[i][j]=INF;}}int u,v,w;while(m--){cin>>u>>v>>w;a[u][v]=min(a[u][v],w);a[v][u]=min(a[v][u],w);}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[i][j]=min(a[i][j],a[i][k]+a[k][j]);}}}for(int i=1;i<=n;i++){a[i][i]=0;for(int j=1;j<=n;j++){cout<<a[i][j]<<' ';}cout<<'\n';}
}
【模板】字符串哈希
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
const int p=53;
const int mod=1e9+7;
int a[N];
char s[N];
int l[N];
int n;
int ans;
int cal(char a[]){int n=strlen(a);l[0]=0;for(int i=1;i<=n;i++)l[i]=(l[i-1]*p+int(a[i]))%mod;return l[n];
}
signed main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s+1);a[i]=cal(s+1);}sort(a+1,a+n+1);for(int i=1;i<=n;i++){if(a[i]!=a[i-1])ans++;}printf("%d",ans);
}
【模板】拓扑排序 / 家谱树
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
vector<int>a[N];
int rd[N];
int cnt,f[N];
void topsort(){queue<int>q;for(int i=1;i<=n;i++)if(rd[i]==0)q.push(i);while(!q.empty()){int x=q.front();q.pop();printf("%d ",x);for(int i=0;i<a[x].size();i++){int v=a[x][i];if(--rd[v]==0){q.push(v);}}}
}
signed main(){scanf("%d",&n);for(int i=1;i<=n;i++){int x;while(1){scanf("%d",&x);if(x==0)break;a[i].push_back(x);rd[x]++;}}topsort();
}
【模板】单调队列
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N];
int q1[N+N];
int q2[N+N];
int head,tail;
int n,m;
signed main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){while(head<=tail&&q1[head]+m<=i)head++;while(head<=tail&&a[i]<a[q1[tail]])tail--;q1[++tail]=i;if(i>=m)printf("%d ",a[q1[head]]);}printf("\n");for(int i=1;i<=n;i++){while(head<=tail&&q2[head]+m<=i)head++;while(head<=tail&&a[i]>a[q2[tail]])tail--;q2[++tail]=i;if(i>=m)printf("%d ",a[q2[head]]);}
}
【模板】单调栈
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+5;
int a[N];
int t[N];
int n;
int head;
signed main(){scanf("%d",&n);for(int i=n;i>=1;i--)scanf("%d",&a[i]);stack<int> k;for(int i=1;i<=n;i++){while(head>0&&a[t[head]]<=a[i])head--;if(head==0)k.push(0);else k.push(n-t[head]+1);t[++head]=i;}while(!k.empty()){printf("%d ",k.top());k.pop();}
}
【模板】三分 | 函数
#include<bits/stdc++.h>
using namespace std;
typedef long double db;
const int N=1e6+5;
const db eps=1e-11;
int n,m;
int a[N],b[N],c[N];
int T;
db check(db x){db ans=a[1]*x*x+b[1]*x+c[1];for(int i=2;i<=n;i++)ans=max(ans,a[i]*x*x+b[i]*x+c[i]);return ans;
}
signed main(){ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];db l=0,r=1000;db mid1,mid2;while(r-l>eps){mid1=l+(r-l)/3.0;mid2=r-(r-l)/3.0;if(check(mid1)>check(mid2))l=mid1;else r=mid2;}printf("%.4Lf\n",check(l));}
}
【模板】字典树
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+5;
int t;
int n,m;
int ch[N][124];
int cnt[N];
int idx=0;
void in(string s){int p=0;for(int i=0;i<s.length();i++){int j=int(s[i]);if(!ch[p][j])ch[p][j]=++idx;p=ch[p][j];cnt[p]++;}
}
int out(string s){int p=0;for(int i=0;i<s.length();i++){int j=int(s[i]);if(!ch[p][j])return 0;p=ch[p][j];}return cnt[p];
}
signed main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);string s;for(int i=0;i<=idx;i++){cnt[i]=0;for(int j=0;j<=123;j++){ch[i][j]=0;}}idx=0;for(int i=1;i<=n;i++){cin>>s;in(s);}for(int i=1;i<=m;i++){cin>>s;printf("%d\n",out(s));}}
}
【模板】并查集
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int f[N];
int n,m;
int T;
int find(int x){if(f[x]!=x)f[x]=find(f[x]);return f[x];
}
signed main(){ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);cin>>n>>m;for(int i=1;i<=n;i++)f[i]=i;while(m--){int op;cin>>op;int x,y;cin>>x>>y;if(op==1){f[find(x)]=find(y);}else{if(f[find(x)]==f[find(y)])cout<<"Y\n";else cout<<"N\n";}}
}
【模板】最小生成树
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5;
struct node{int u,v,w;
}a[N];
int f[N];
int cnt;
int n,m;
int find(int x){if(f[x]!=x)f[x]=find(f[x]);return f[x];
}
bool cmp(node a,node b){return a.w<b.w;
}
int s(){sort(a+1,a+1+cnt,cmp);for(int i=1;i<=cnt;i++)f[i]=i;int sum=0;for(int i=1;i<=cnt;i++){int u=a[i].u;int v=a[i].v;int w=a[i].w;if(find(u)==find(v))continue;else{sum+=w;f[find(u)]=find(v);}}return sum;
}
int vis[N];
vector<int>vs[N];
void dfs(int x){vis[x]=1;for(int i=0;i<vs[x].size();i++){if(vis[vs[x][i]]==0)dfs(vs[x][i]);}
}
signed main(){ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);cin>>n>>m;while(m--){int x,y,z;cin>>x>>y>>z;vs[x].push_back(y);vs[y].push_back(x);a[++cnt]=node{x,y,z};}dfs(1);for(int i=1;i<=n;i++)if(!vis[i]){cout<<"orz";return 0;}cout<<s();
}
【模板】负环
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node{int to,dis;
};
int T;
vector<node>a[N];
int dis[N];
int vis[N];
int cnt[N];
int n,m;
queue<int>q;
bool spfa(){for(int i=1;i<=n;i++)dis[i]=2147483647;dis[1]=0;q.push(1);vis[1]=1;while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(int i=0;i<a[x].size();i++){int v=a[x][i].to;int w=a[x][i].dis;if(dis[v]>dis[x]+w){dis[v]=dis[x]+w;if(vis[v]==0){vis[v]=1;q.push(v);cnt[v]++;}if(cnt[v]>n)return true;}}}return false;
}
signed main(){scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);memset(vis,0,sizeof(vis));memset(cnt,0,sizeof(vis));while(!q.empty())q.pop();for(int i=1;i<=n;i++)a[i].clear();for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);a[u].push_back(node{v,w});if(w>=0)a[v].push_back(node{u,w});}if(spfa())printf("YES\n");else printf("NO\n");}
}
【模板】堆
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N];
int n;
int T;
priority_queue<int,vector<int>,greater<int> >q;
signed main(){ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);cin>>T;while(T--){int op;cin>>op;if(op==1){int x;cin>>x;q.push(x);}else if(op==2){cout<<q.top()<<'\n';}else q.pop();}
}
【模板】单源最短路径
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,s;
struct node{int to,dis;friend bool operator <(node a,node b){return a.dis>b.dis;}
};
priority_queue<node>q;
vector<node>a[N];
int dis[N];
int vis[N];
void dij(){for(int i=1;i<=n;i++)dis[i]=INT_MAX;dis[s]=0;q.push(node{s,0});while(!q.empty()){node t=q.top();q.pop();int x=t.to;if(vis[x]==1)continue;vis[x]=1;for(int i=0;i<a[x].size();i++){int y=a[x][i].to;int z=a[x][i].dis;dis[y]=min(dis[y],dis[x]+z);if(vis[y]==0)q.push(node{y,dis[y]});}}
}
signed main(){scanf("%lld%lld%lld",&n,&m,&s);int u,v,w;for(int i=1;i<=m;i++){scanf("%lld%lld%lld",&u,&v,&w);a[u].push_back(node{v,w});}dij();for(int i=1;i<=n;i++)printf("%lld ",dis[i]);
}
【模板】差分约束
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
struct node{int to,dis;
};
vector<node>a[N];
int n,m;
int vis[N];
int dis[N];
int cnt[N];
queue<int>q;
bool spfa(){for(int i=1;i<=n;i++)dis[i]=2147483647;dis[0];q.push(0);vis[0]=1;while(!q.empty()){int x=q.front();vis[x]=0;q.pop();for(int i=0;i<a[x].size();i++){int v=a[x][i].to;int w=a[x][i].dis;if(dis[v]>dis[x]+w){dis[v]=dis[x]+w;if(vis[v]==0){vis[v]=1;cnt[v]++;q.push(v);}if(cnt[v]>n)return true;}}}return false;
}
signed main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);a[v].push_back(node{u,w});}for(int i=1;i<=n;i++){a[0].push_back(node{i,0});}if(spfa()){printf("NO");}else{for(int i=1;i<=n;i++)printf("%d ",dis[i]);}
}
【模板】边双连通分量
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,k;
int T;
int dfn[N];
int low[N];
int idx;
int f[N];
int cnt;
int cntt;
vector<pair<int,int> >a[N];
vector<int>ans[N];
void dfs(int x,int fa){dfn[x]=low[x]=++idx;f[++cnt]=x;for(int i=0;i<a[x].size();i++){pair<int,int> y=a[x][i];if(y.second==(fa^1))continue;if(dfn[y.first]==0){dfs(y.first,y.second);low[x]=min(low[x],low[y.first]);}else{low[x]=min(dfn[y.first],low[x]);}}if(dfn[x]==low[x]){ans[++cntt].push_back(x);while(f[cnt]!=x)ans[cntt].push_back(f[cnt--]);cnt--;}
}
signed main(){ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;a[u].push_back(make_pair(v,i<<1));a[v].push_back(make_pair(u,i<<1|1));}for(int i=1;i<=n;i++){if(!dfn[i])dfs(i,0);}cout<<cntt<<'\n';for(int i=1;i<=cntt;i++){cout<<ans[i].size()<<' ';for(int j=0;j<ans[i].size();j++)cout<<ans[i][j]<<' ';}
}
【模板】树状数组 1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
ll a[N];
ll f[N];
ll n,m;
int lowbit(ll x){return x&-x;
}
void change(ll x,ll k){while(x<=n)f[x]+=k,x+=lowbit(x);
}
ll out(ll x){int sum=0;while(x)sum+=f[x],x-=lowbit(x);return sum;
}
signed main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);change(i,a[i]);}while(m--){int op;ll x,y;scanf("%d",&op);scanf("%lld%lld",&x,&y);if(op==1){change(x,y);}else{printf("%lld\n",out(y)-out(x-1));}}
}
【模板】KMP
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int ne[N];
char a[N];
char c[N];
signed main(){cin>>c+1;cin>>a+1;int n=strlen(a+1);int m=strlen(c+1);ne[1]=0;for(int i=2,j=0;i<=n;i++){while(j&&a[i]!=a[j+1])j=ne[j];if(a[i]==a[j+1])j++;ne[i]=j;}for(int i=1,j=0;i<=m;i++){while(j&&c[i]!=a[j+1])j=ne[j];if(c[i]==a[j+1])j++;if(j==n)printf("%d\n",i-n+1);}for(int i=1;i<=n;i++)printf("%d ",ne[i]);
}
【模板】树状数组 2
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N];
int f[N];
int n,m;
int lowbit(int x){return x&(-x);
}
void change(int x,int k){while(x<=n)f[x]+=k,x+=lowbit(x);
}
int c(int x){int res=0;while(x)res+=f[x],x-=lowbit(x);return res;
}
signed main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}while(m--){int z;scanf("%d",&z);if(z==1){int x,y,k;scanf("%d%d%d",&x,&y,&k);change(x,k);change(y+1,-k);}else{int x;scanf("%d",&x);printf("%d\n",a[x]+c(x));}}
}
【模板】线段树 1
#include<bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N=1e6+5;
const int M=1e3+5;
int n,m,k;
int T;
int a[N];
struct node{int l,r,ans,add;
}f[4*N];
void build(int p,int l,int r){f[p]={l,r,a[l],0};if(l==r)return;int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);f[p].ans=f[lc].ans+f[rc].ans;
}
void down(int p){if(f[p].add){f[lc].ans+=(f[lc].r-f[lc].l+1)*f[p].add;f[rc].ans+=(f[rc].r-f[rc].l+1)*f[p].add;f[lc].add+=f[p].add;f[rc].add+=f[p].add;f[p].add=0;}
}
void change(int p,int l,int r,int k){if(f[p].l>=l&&f[p].r<=r){f[p].ans+=(f[p].r-f[p].l+1)*k;f[p].add+=k;return;}int mid=f[p].l+f[p].r>>1;down(p);if(l<=mid)change(lc,l,r,k);if(mid<r)change(rc,l,r,k);f[p].ans=f[lc].ans+f[rc].ans;
}
int cha(int p,int l,int r){if(f[p].l>=l&&f[p].r<=r){return f[p].ans;}int mid=f[p].l+f[p].r>>1;int ans=0;down(p);if(l<=mid)ans+=cha(lc,l,r);if(mid<r)ans+=cha(rc,l,r);return ans;
}
signed main(){ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}build(1,1,n);int x,y,k;while(m--){int op;cin>>op;if(op==1){cin>>x>>y>>k;change(1,x,y,k);}else{cin>>x>>y;cout<<cha(1,x,y)<<'\n';}}
}
【模板】线段树 2
#include<bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N=1e6+5;
const int M=1e3+5;
int n,m,k,mod;
int T;
int a[N];
struct node{int l,r,ans,add,mo;
}f[4*N];
void build(int p,int l,int r){f[p]={l,r,a[l]%mod,0,1};if(l==r)return;int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);f[p].ans=(f[lc].ans+f[rc].ans)%mod;
}
void down(int p){f[lc].ans=((f[p].mo*f[lc].ans)%mod+((f[lc].r-f[lc].l+1)*f[p].add)%mod)%mod;f[rc].ans=((f[p].mo*f[rc].ans)%mod+((f[rc].r-f[rc].l+1)*f[p].add)%mod)%mod;f[lc].add=((f[lc].add*f[p].mo)%mod+f[p].add)%mod;f[rc].add=((f[rc].add*f[p].mo)%mod+f[p].add)%mod;f[lc].mo=(f[lc].mo*f[p].mo)%mod;f[rc].mo=(f[rc].mo*f[p].mo)%mod;f[p].add=0;f[p].mo=1;
}
void change(int p,int l,int r,int k){if(f[p].l>=l&&f[p].r<=r){f[p].ans=(f[p].ans+(f[p].r-f[p].l+1)*k)%mod;f[p].add=(f[p].add+k)%mod;return;}int mid=f[p].l+f[p].r>>1;down(p);if(l<=mid)change(lc,l,r,k);if(mid<r)change(rc,l,r,k);f[p].ans=(f[lc].ans+f[rc].ans)%mod;
}
void mo(int p,int l,int r,int k){if(f[p].l>=l&&f[p].r<=r){f[p].ans=(f[p].ans*k)%mod;f[p].mo=(f[p].mo*k)%mod;f[p].add=(f[p].add*k)%mod;return;}int mid=f[p].l+f[p].r>>1;down(p);if(l<=mid)mo(lc,l,r,k);if(mid<r)mo(rc,l,r,k);f[p].ans=(f[lc].ans+f[rc].ans)%mod;
}
int cha(int p,int l,int r){if(f[p].l>=l&&f[p].r<=r){return f[p].ans%mod;}int mid=f[p].l+f[p].r>>1;int ans=0;down(p);if(l<=mid)ans=(ans+cha(lc,l,r))%mod;if(mid<r)ans=(ans+cha(rc,l,r))%mod;return ans;
}
signed main(){ios::sync_with_stdio(0);cin>>n>>m>>mod;for(int i=1;i<=n;i++){cin>>a[i];}build(1,1,n);int x,y,k;while(m--){int op;cin>>op;if(op==1){cin>>x>>y>>k;mo(1,x,y,k);}else if(op==2){cin>>x>>y>>k;change(1,x,y,k);}else{cin>>x>>y;cout<<cha(1,x,y)<<'\n';}}
}
【模板】割点（割顶）
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m;
int dfn[N];
int vis[N];
int low[N];
int cut[N];
vector<int>a[N];
int cnt;
int times;
void tarjan(int x,int root){vis[x]=1;dfn[x]=low[x]=++times;int s=0;for(int i=0;i<a[x].size();i++){int y=a[x][i];if(dfn[y]==0){s++;tarjan(y,root);low[x]=min(low[x],low[y]);if(x!=root&&low[y]>=dfn[x])cut[x]=1;if(x==root&&s>=2)cut[x]=1;}else{low[x]=min(low[x],dfn[y]);}}
}
main(){scanf("%d%d",&n,&m);int u,v;for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);a[u].push_back(v);a[v].push_back(u);}for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i,i);int cnt=0;for(int i=1;i<=n;i++)if(cut[i])cnt++;printf("%d\n",cnt);for(int i=1;i<=n;i++)if(cut[i])printf("%d ",i);
}
【模板】点双连通分量
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,k;
int T;
vector<int>a[N];
int low[N],dfn[N];
int tt;
int cnt;
int top;
int t[N];
vector<int>f[N];
void dfs(int u,int fa){int son=0;low[u]=dfn[u]=++tt;t[++top]=u;for(int i=0;i<a[u].size();i++){int v=a[u][i];if(dfn[v]==0){son++;dfs(v,u);low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]){cnt++;while(t[top+1]!=v)f[cnt].push_back(t[top--]);f[cnt].push_back(u);}}else if(v!=fa){low[u]=min(low[u],dfn[v]);}}if(fa==0&&son==0)f[++cnt].push_back(u);
}
signed main(){ios::sync_with_stdio(0);cin>>n>>m;int u,v;for(int i=1;i<=m;i++){cin>>u>>v;a[u].push_back(v);a[v].push_back(u);}for(int i=1;i<=n;i++){if(dfn[i])continue;dfs(i,0);}cout<<cnt<<'\n';for(int i=1;i<=cnt;i++){cout<<f[i].size()<<' ';for(int j=0;j<f[i].size();j++)cout<<f[i][j]<<' ';cout<<'\n';}
}
【模板】三维偏序
#include<bits/stdc++.h>
#define xx x&-x
using namespace std;
const int N=1e5+5;
const int M=1e3+5;
int n,m,k;
int T;
struct node{int a,b,c,cnt,ans;
}e[N],t[N];
int ans[N];
int bit[N];
bool cmpA(node a,node b){return a.a<b.a||(a.a==b.a&&a.b<b.b)||(a.a==b.a&&a.b==b.b&&a.c<b.c);
}
bool cmpB(node a,node b){return a.b<b.b||(a.b==b.b&&a.c<b.c);
}
void update(int x,int v){while(x<=k){bit[x]+=v;x+=xx;}
}
int query(int x){int res=0;while(x){res+=bit[x];x-=xx;}return res;
}
void cdq(int l,int r){if(l==r)return;int mid=l+r>>1;cdq(l,mid);cdq(mid+1,r);sort(e+l,e+mid+1,cmpB);sort(e+mid+1,e+r+1,cmpB);int i=l,j=mid+1;while(j<=r){while(i<=mid&&e[i].b<=e[j].b){update(e[i].c,e[i].cnt);i++;}e[j].ans+=query(e[j].c);j++;}for(int p=l;p<=i-1;p++)update(e[p].c,-e[p].cnt);
}
signed main(){ios::sync_with_stdio(0);cin>>n>>k;for(int i=1;i<=n;i++){cin>>e[i].a>>e[i].b>>e[i].c;e[i].cnt=1;}sort(e+1,e+1+n,cmpA);int m=1;for(int i=2;i<=n;i++){if(e[i].a==e[m].a&&e[i].b==e[m].b&&e[i].c==e[m].c){e[m].cnt++;}else{e[++m]=e[i];}}cdq(1,m);for(int i=1;i<=m;i++)ans[e[i].ans+e[i].cnt]+=e[i].cnt;for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
}
【模板】整体二分
#include<bits/stdc++.h>
#define int long long
#define xx x&-x
using namespace std;
const int N=1e6+5;
const int M=1e3+5;
int n,m,k;
int T;
struct node{int l,r,k,id,op;
}a[N],ql[N],qr[N];
int answer[N];
int bit[N];
int cnt;
void change(int x,int p){while(x<=cnt){bit[x]+=p;x+=xx;}
}
int query(int x){int res=0;while(x){res+=bit[x];x-=xx;}return res;
}
void f(int l,int r,int N,int M){if(N>=M)return;if(l==r){for(int i=N;i<=M;i++){if(a[i].op==2)answer[a[i].id]=r;}return;}int mid=l+r>>1;int t1=0,t2=0;for(int i=N;i<=M;i++){if(a[i].op==1){if(mid>=a[i].l){ql[++t1]=a[i];change(a[i].id,1);}else{qr[++t2]=a[i];}}else{int x=query(a[i].r)-query(a[i].l-1);if(x>=a[i].k){ql[++t1]=a[i];}else{a[i].k-=x;qr[++t2]=a[i];}}}for(int i=1;i<=t1;i++){a[i+N-1]=ql[i];if(ql[i].op==1)change(ql[i].id,-1);}for(int i=1;i<=t2;i++){a[i+N+t1-1]=qr[i];}f(l,mid,N,N+t1-1);f(mid+1,r,N+t1,M);
}
signed main(){ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i].l;a[i].id=i;a[i].op=1;}cnt=n;for(int i=1;i<=m;i++){cnt++;cin>>a[cnt].l>>a[cnt].r>>a[cnt].k;a[cnt].id=i;a[cnt].op=2;}f(-1e9,1e9,1,cnt);for(int i=1;i<=m;i++)cout<<answer[i]<<'\n';
}