个人代码基础模板
Aurelia_Veil · · 算法·理论
Aurelia_Veil 好菜呀
欧拉回路
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+111;
int n,m;
vector<int>g[N];
stack<int>ans;
int in[N],out[N];
int thi[N];
void FC(int u){
for(int i=thi[u];i<g[u].size();i=thi[u]){
int v=g[u][i];
thi[u]=i+1;
FC(v);
}
ans.push(u);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
in[y]++;
out[x]++;
g[x].push_back(y);
}
int cntin=0,cntout=0,top=1;
for(int i=1;i<=n;i++){
if(abs(in[i]-out[i])>=2){
printf("No");
return 0;
}
if(in[i]==out[i]+1){
cntin++;
}
if(in[i]+1==out[i]){
top=i;
cntout++;
}
}
if(cntin>=2||cntout>=2){
printf("No");
return 0;
}
for(int i=1;i<=n;i++){
sort(g[i].begin(),g[i].end());
}
FC(top);
while(!ans.empty()){
printf("%d ",ans.top());
ans.pop();
}
return 0;
}快读快写
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define itn int
#define fro for
#define scnaf scanf
#define snacf scanf
#define prinf printf
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline string readS(){
string s;
char ch=getchar();
while(ch==' '||ch=='\n'){
ch=getchar();
}
while(ch!=' '&&ch!='\n'){
s+=ch;
ch=getchar();
}
return s;
}
inline string readSL(){
string s;
s.clear();
char ch=getchar();
while(ch=='\n'){
ch=getchar();
}
while(ch!='\n'){
s+=ch;
ch=getchar();
}
return s;
}
inline void readC(char s[]){
int tot=0;
char ch=getchar();
while(ch==' '||ch=='\n'){
ch=getchar();
}
while(ch!=' '&&ch!='\n'){
s[tot++]=ch;
ch=getchar();
}
}
inline char readc(){
char c=getchar();
while(c==' '||c=='\n'){
c=getchar();
}
return c;
}
inline void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9){
write(x/10);
}
putchar(x%10+'0');
return;
}
inline void writeS(string x){
int len=x.length();
for(int i=0;i<len;++i){
putchar(char(x[i]));
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}#include<bits/stdc++.h>
#include<unistd.h>
using namespace std;
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
constexpr int BUFSIZE=1<<14;
char ibuf[BUFSIZE],*ibg=ibuf+BUFSIZE,obuf[BUFSIZE],*obg=obuf;
const char *ied=ibuf+BUFSIZE,*oed=obuf+BUFSIZE;
#define INLINE inline __attribute__ ((always_inline))
//INLINE char get(){
// if(ibg==ied){
// cin.read(ibg=ibuf,BUFSIZE);
// }
// return *ibg++;
//}
INLINE void put(char a){
if(obg==oed){
write(1,obg=obuf,BUFSIZE);
}
*(obg++)=a;
}
INLINE int read(){
if(ied-ibg<=15){unsigned len=ied-ibg;
memmove(ibuf,ibg,len);
cin.read((ibg=ibuf)+len,BUFSIZE-len);
}
unsigned a=0;char c=*ibg++;bool f=1;
while(c<'0'||c>'9'){
if(c=='-')f=0;
//if(c==0)break;
c=*ibg++;
}
while(c>='0'&&c<='9'){
a=(a<<1)+(a<<3)+(c^48);
c=*ibg++;//cerr<<c<<' ';
}
return f?a:(~(a-1));
}
constexpr unsigned lg10[15]={1,10,100,1000,10000,100000,1000000,
10000000,100000000,1000000000};
INLINE void write(unsigned a){
if((int)(a)<0){
put('-');
a=(~(a-1));
}
if(a==0){
put('0');put('\n');return;
}
const unsigned *p=upper_bound(lg10,lg10+10,a)-1;
for(;p>=lg10;p--){
put(a/(*p)+'0');a%=(*p);
}
put('\n');
}
//#define int long long
signed main(){
//......
write(1,obuf,obg-obuf);
return 0;
}
LCA
倍增法：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+111;
int dep[N];
int net[N][37];
vector<int>g[N];
void dfs(int u,int dad){
dep[u]=dep[dad]+1;
net[u][0]=dad;
for(int i=1;i<=27;i++){
net[u][i]=net[net[u][i-1]][i-1];
}
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v==dad){
continue;
}
dfs(v,u);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]){
swap(x,y);
}
for(int i=27;i>=0;i--){
if(dep[net[x][i]]>=dep[y]){
x=net[x][i];
}
if(x==y){
return x;
}
}
for(int i=27;i>=0;i--){
if(net[x][i]!=net[y][i]){
x=net[x][i];
y=net[y][i];
}
}
return net[x][0];
}
int main(){
int n,m,begi;
scanf("%d",&n);
scanf("%d%d",&m,&begi);
int x,y;
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs(begi,0);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}树剖法
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6;
int n,m,begi;
int a[N],b[N];
vector<int>g[N];
int tp[N],son[N],dfn[N];
int siz[N],dep[N],fa[N];
int tot;
void dfs1(int u,int dad){
dep[u]=dep[dad]+1;
siz[u]=1;
fa[u]=dad;
int maxx=-1,maxi=-1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v==dad){
continue;
}
dfs1(v,u);
if(siz[v]>maxx){
maxi=v;
maxx=siz[v];
}
siz[u]+=siz[v];
}
son[u]=maxi;
}
void dfs2(int u,int dad,int top){
dfn[u]=++tot;
tp[u]=top;
if(son[u]!=-1){
dfs2(son[u],u,top);
}
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v==dad||v==son[u]){
continue;
}
dfs2(v,u,v);
}
}
int lca(int x,int y){
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]){
swap(x,y);
}
x=fa[tp[x]];
}
if(dep[x]>dep[y]){
swap(x,y);
}
return x;
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&begi);
for(int i=1;i<n;i++){
int x,y;
scanf("%lld%lld",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs1(begi,0);
dfs2(begi,0,begi);
while(m--){
int x,y;
scanf("%lld%lld",&x,&y);
printf("%lld\n",lca(x,y));
}
return 0;
}线段树：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6;
int n,m;
struct tree{
struct pai{
long long thi,tag;
};
pai t[N];
int _merge(int a,int b){
return a+b;
}
pai merge(pai a,pai b){
pai ret{_merge(a.thi,b.thi),0};
return ret;
}
void push_down(int k,int cl,int cr){
if(t[k].tag==0){
return;
}
int lc=k<<1,rc=lc+1;
int mid=(cl+cr)>>1;
t[lc].tag+=t[k].tag;
t[rc].tag+=t[k].tag;
t[lc].thi+=(mid-cl+1)*t[k].tag;
t[rc].thi+=(cr-mid)*t[k].tag;
t[k].tag=0;
}
void build(int a[],int k,int cl,int cr){
if(cl==cr){
t[k].thi=a[cl];
return;
}
int lc=k<<1,rc=lc+1;
int mid=(cl+cr)>>1;
build(a,lc,cl,mid);
build(a,rc,mid+1,cr);
t[k]=merge(t[lc],t[rc]);
}
void init(int a[]){
build(a,1,1,n);
}
long long qry(int k,int l,int r,int cl,int cr){
if(cl>r||cr<l||l>r){
return 0;
}
if(cl>=l&&cr<=r){
return t[k].thi;
}
int lc=k<<1,rc=lc+1;
int mid=(cl+cr)>>1;
push_down(k,cl,cr);
return _merge(qry(lc,l,r,cl,mid),qry(rc,l,r,mid+1,cr));
}
void modify(int k,int l,int r,int cl,int cr,long long x){
if(cl>r||cr<l||l>r){
return;
}
if(l<=cl&&r>=cr){
t[k].tag+=x;
t[k].thi+=x*(cr-cl+1);
return;
}
int lc=k<<1,rc=lc+1;
int mid=(cl+cr)>>1;
push_down(k,cl,cr);
modify(lc,l,r,cl,mid,x);
modify(rc,l,r,mid+1,cr,x);
t[k]=merge(t[lc],t[rc]);
}
}tr;
int a[N];
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
tr.init(a);
for(int i=1;i<=m;i++){
int k;
scanf("%lld",&k);
if(k==1){
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
tr.modify(1,x,y,1,n,z);
}else{
int x,y;
scanf("%lld%lld",&x,&y);
printf("%lld\n",tr.qry(1,x,y,1,n));
}
}
return 0;
}树状数组：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+101;
long long a[N];
int n,m;
struct trma{
long long tree[N<<1];
int lowbit(int x){
return x&(-x);
}
void add(int x,int y){
for(int i=x;i<=n;i+=lowbit(i)){
tree[i]+=y;
}
}
long long sum(int x){
long long sum=0;
for(int i=x;i!=0;i-=lowbit(i)){
sum+=tree[i];
}
return sum;
}
}tr;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
tr.add(i,a[i]-a[i-1]);
}
for(int i=1;i<=m;i++){
int k;
scanf("%d",&k);
if(k==1){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
tr.add(x,z);
tr.add(y+1,-z);
}else{
int x;
scanf("%d",&x);
printf("%lld\n",tr.sum(x));
}
}
return 0;
}ST表：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[200001];
int loge[200001],st[200001][31];
void init(){
for(int i=2;i<=n;i++){
loge[i]=loge[i>>1]+1;
}
for(int i=1;i<=n;i++){
st[i][0]=a[i];
}
for(int i=1;(1<<i)<=n;i++){
for(int j=1;j<=n-(1<<i)+1;j++){
st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
}
int find(int x,int y){
int l=loge[y-x+1];
return min(st[x][l],st[y-(1<<l)+1][l]);
}
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
init();
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
printf("%d ",find(x,y));
}
return 0;
}动态开点线段树：
#include<bits/stdc++.h>
using namespace std;
const int N=6.4e6+111;
int mod;
struct pai{
int thi,tag,lef,rig;
};
int n,m;
struct tree{
pai t[N];
int tot;
void in_it(int x){
t[x]={0,0,0,0};
}
void _init(){
tot=1;
in_it(1);
}
int _merge(int a,int b){
return (a+b)%mod;
}
pai merge(pai a,pai b,pai c){
pai ret{_merge(a.thi,b.thi),0,c.lef,c.rig};
return ret;
}
void push_down(int k,int cl,int cr){
if(t[k].tag==0){
return;
}
if(t[k].lef==0){
t[k].lef=++tot;
in_it(t[k].lef);
}
if(t[k].rig==0){
t[k].rig=++tot;
in_it(t[k].rig);
}
int lc=t[k].lef,rc=t[k].rig;
int mid=(cl+cr)>>1;
(t[lc].tag+=t[k].tag)%=mod;
(t[rc].tag+=t[k].tag)%=mod;
(t[lc].thi+=(mid-cl+1)%mod*1ll*t[k].tag%mod)%=mod;
(t[rc].thi+=(cr-mid)%mod*1ll*t[k].tag%mod)%=mod;
t[k].tag=0;
}
int qry(int k,int l,int r,int cl,int cr){
if(k==0){
return 0;
}
if(cl>=l&&cr<=r){
return t[k].thi%mod;
}
int mid=(cl+cr)>>1;
push_down(k,cl,cr);
int lc=t[k].lef,rc=t[k].rig;
int ansl=0,ansr=0;
if(mid>=l){
ansl=qry(lc,l,r,cl,mid)%mod;
}
if(mid+1<=r){
ansr=qry(rc,l,r,mid+1,cr)%mod;
}
return _merge(ansl,ansr);
}
void modify(int& k,int l,int r,int cl,int cr,int x){
// printf("|%d %d %d %d %d %d\n",k,l,r,cl,cr,x);
if(k==0){
k=++tot;
in_it(k);
}
if(l<=cl&&r>=cr){
(t[k].tag+=x%mod)%=mod;
(t[k].thi+=x%mod*1ll*(cr-cl+1)%mod)%=mod;
return;
}
int mid=(cl+cr)>>1;
push_down(k,cl,cr);
if(mid>=l){
modify(t[k].lef,l,r,cl,mid,x);
}
if(mid+1<=r){
modify(t[k].rig,l,r,mid+1,cr,x);
}
t[k]=merge(t[t[k].lef],t[t[k].rig],t[k]);
}
}tr;
signed main(){
scanf("%d%d",&m,&mod);
tr._init();
for(int i=1;i<=m;i++){
int k;
scanf("%d",&k);
if(k==1){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
int kl=1;
tr.modify(kl,x,y,1,1000000000,z);
}else{
int x,y;
scanf("%d%d",&x,&y);
int kl=1;
printf("%d\n",tr.qry(kl,x,y,1,1000000000));
}
}
return 0;
}可持久化线段树：
#include<bits/stdc++.h>
using namespace std;
const int N=2.3e7+111;
int n,m;
int a[N];
struct tr{
struct tree{
int l,r,u,x;
}tr[N];
int tot=0,ver[N];
void merge(int u){
tr[u].x=tr[tr[u].l].x+tr[tr[u].r].x;
}
int add(int u){
tr[++tot]=tr[u];
return tot;
}
int build(int u,int l,int r){
u=++tot;
if(l==r){
tr[u].x=a[l];
return u;
}
int mid=(l+r)/2;
tr[u].l=build(tr[u].l,l,mid);
tr[u].r=build(tr[u].r,mid+1,r);
merge(u);
return u;
}
int adtree(int u,int l,int r,int x,int y){
u=add(u);
if(l==r){
tr[u].x=y;
return u;
}
int mid=(l+r)/2;
if(x<=mid){
tr[u].l=adtree(tr[u].l,l,mid,x,y);
}else{
tr[u].r=adtree(tr[u].r,mid+1,r,x,y);
}
merge(u);
return u;
}
int qry(int u,int l,int r,int cl,int cr){
if(cl>=l&&cr<=r){
// cerr<<l<<" "<<r<<" "<<tr[u].x<<"\n";
return tr[u].x;
}
int mid=(cl+cr)/2;
int ans=0;
if(mid>=l){
ans+=qry(tr[u].l,l,r,cl,mid);
}
if(mid+1<=r){
ans+=qry(tr[u].r,l,r,mid+1,cr);
}
return ans;
}
}b;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
b.ver[0]=b.build(0,1,n);
for(int i=1;i<=m;i++){
int x,op;
scanf("%d%d",&x,&op);
if(op==1){
int y,z;
scanf("%d%d",&y,&z);
b.ver[i]=b.adtree(b.ver[x],1,n,y,z);
}else{
int y;
scanf("%d",&y);
printf("%d\n",b.qry(b.ver[x],y,y,1,n));
b.ver[i]=b.ver[x];
}
}
return 0;
} 平衡树（权值线段树模拟）
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+111;
struct pai{
int thi,tag,lef,rig;
};
long long n,m;
struct tree{
pai t[N];
int tot;
void in_it(int x){
t[x]={0,0,0,0};
}
void _init(){
tot=1;
in_it(1);
}
int _merge(int a,int b){
return a+b;
}
pai merge(pai a,pai b,pai c){
pai ret{_merge(a.thi,b.thi),0,c.lef,c.rig};
return ret;
}
void push_down(int k,long long cl,long long cr){
if(t[k].tag==0){
return;
}
if(t[k].lef==0){
t[k].lef=++tot;
in_it(t[k].lef);
}
if(t[k].rig==0){
t[k].rig=++tot;
in_it(t[k].rig);
}
int lc=t[k].lef,rc=t[k].rig;
long long mid=(cl+cr)>>1;
t[lc].tag+=t[k].tag;
t[rc].tag+=t[k].tag;
t[lc].thi+=(mid-cl+1)*1ll*t[k].tag;
t[rc].thi+=(cr-mid)*1ll*t[k].tag;
t[k].tag=0;
}
int qry(int k,long long l,long long r,long long cl,long long cr){
if(k==0){
return 0;
}
if(cl>=l&&cr<=r){
return t[k].thi;
}
long long mid=(cl+cr)>>1;
push_down(k,cl,cr);
int lc=t[k].lef,rc=t[k].rig;
int ansl=0,ansr=0;
if(mid>=l){
ansl=qry(lc,l,r,cl,mid);
}
if(mid+1<=r){
ansr=qry(rc,l,r,mid+1,cr);
}
return _merge(ansl,ansr);
}
int qry2(int k,long long cl,long long cr,int x){
if(k==0){
return 0;
}
if(cl==cr){
return cl;
}
long long mid=(cl+cr)>>1;
push_down(k,cl,cr);
int lc=t[k].lef,rc=t[k].rig;
// cerr<<t[lc].thi<<" "<<t[rc].thi<<"|"<<x<<"|"<<lc<<" "<<rc<<"|"<<cl<<" "<<cr<<"\n";
if(lc!=0&&t[lc].thi>=x){
return qry2(lc,cl,mid,x);
}else{
x-=t[lc].thi;
return qry2(rc,mid+1,cr,x);
}
}
void modify(int& k,long long l,long long r,long long cl,long long cr,int x){
if(k==0){
k=++tot;
in_it(k);
}
if(l<=cl&&r>=cr){
t[k].tag+=x;
t[k].thi+=x*1ll*(cr-cl+1);
return;
}
long long mid=(cl+cr)>>1;
push_down(k,cl,cr);
if(mid>=l){
modify(t[k].lef,l,r,cl,mid,x);
}
if(mid+1<=r){
modify(t[k].rig,l,r,mid+1,cr,x);
}
t[k]=merge(t[t[k].lef],t[t[k].rig],t[k]);
}
}tr;
int a[N];
signed main(){
n=3e7;
scanf("%lld",&m);
int k;
tr._init();
for(int i=1;i<=m;i++){
k=1;
int op,x;
scanf("%lld%lld",&op,&x);
if(op!=4){
x+=1e7+1;
}
if(op==1){
tr.modify(k,x,x,1,n,1);
}
if(op==2){
tr.modify(k,x,x,1,n,-1);
}
if(op==3){
printf("%lld\n",tr.qry(1,1,x-1,1,n)+1);
}
if(op==4){
printf("%lld\n",(int)(tr.qry2(1,1,n,x)-1e7-1));
}
if(op==5){
int y=tr.qry(1,1,x-1,1,n);
printf("%lld\n",(int)(tr.qry2(1,1,n,y)-1e7-1));
}
if(op==6){
int y=tr.qry(1,1,x,1,n);
printf("%lld\n",(int)(tr.qry2(1,1,n,y+1)-1e7-1));
}
}
return 0;
}并查集：
struct disjoint_set{
int fa[N];
void _init(){
for(int i=0;i<=N-11;i++){
fa[i]=i;
}
}
int find(int x){
if(fa[x]!=x){
fa[x]=find(fa[x]);
}
return fa[x];
}
bool make(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx==fy){
return 0;
}
fa[fx]=fy;
return 1;
}
};线段树合并：
#include<bits/stdc++.h>
using namespace std;
const int N=6.4e6+111;
struct pai{
int thi,tag,lef,rig;
};
int n,m;
int a[N],a_[N];
struct tree{
pai t[N];
int tot=0,grd=0;
int ver[N];
void in_it(int x){
t[x]={0,0,0,0};
}
void _init(int grd){
tot++;
ver[grd]=tot;
in_it(tot);
}
int _merge(int a,int b){
return a+b;
}
pai merge(pai a,pai b,pai c){
pai ret{_merge(a.thi,b.thi),0,c.lef,c.rig};
return ret;
}
void push_down(int k,int cl,int cr){
if(t[k].tag==0){
return;
}
if(t[k].lef==0){
t[k].lef=++tot;
in_it(t[k].lef);
}
if(t[k].rig==0){
t[k].rig=++tot;
in_it(t[k].rig);
}
int lc=t[k].lef,rc=t[k].rig;
int mid=(cl+cr)>>1;
t[lc].tag=t[k].tag;
t[rc].tag=t[k].tag;
t[lc].thi=t[k].tag*(mid-cl+1);
t[rc].thi=t[k].tag*(cr-mid);
t[k].tag=0;
}
int _make(int ka,int kb,int l,int r){
if(ka==0&&kb==0){
return 0;
}
if(ka==0){
// printf("|kb|id=%d l=%d r=%d thi=%d\n",kb,l,r,t[kb].thi);
return kb;
}
if(kb==0){
// printf("|ka|id=%d l=%d r=%d thi=%d\n",ka,l,r,t[ka].thi);
return ka;
}
if(l==r){
// printf("|kab|id=[%d,%d] l=%d r=%d|ll=%d rr=%d\n",ka,kb,l,r,t[ka].thi,t[kb].thi);
t[ka].thi=_merge(t[ka].thi,t[kb].thi);
return ka;
}
push_down(ka,l,r);
push_down(kb,l,r);
int mid=(l+r)/2;
t[ka].lef=_make(t[ka].lef,t[kb].lef,l,mid);
t[ka].rig=_make(t[ka].rig,t[kb].rig,mid+1,r);
t[ka]=merge(t[t[ka].lef],t[t[ka].rig],t[ka]);
// printf("|%d|%d %d|l=%d r=%d thi=%d\n",ka,l,r,t[ka].lef,t[ka].rig,t[ka].thi);
return ka;
}
void make(int &ka,int kb,int l,int r){
ka=_make(ka,kb,l,r);
}
int qry(int k,int l,int r,int cl,int cr){
if(k==0){
return 0;
}
if(cl>=l&&cr<=r){
return t[k].thi;
}
int mid=(cl+cr)>>1;
push_down(k,cl,cr);
int lc=t[k].lef,rc=t[k].rig;
int ansl=0,ansr=0;
if(mid>=l){
ansl=qry(lc,l,r,cl,mid);
}
if(mid+1<=r){
ansr=qry(rc,l,r,mid+1,cr);
}
return _merge(ansl,ansr);
}
int rank(int k,int cl,int cr,int x){
if(k==0){
return -1;
}
if(cl==cr){
return cl;
}
int mid=(cl+cr)>>1;
push_down(k,cl,cr);
int lc=t[k].lef,rc=t[k].rig;
// printf("||%d|%d %d|l=%d r=%d|ll=%d rr=%d x=%d\n",k,cl,cr,lc,rc,t[lc].thi,t[rc].thi,x);
if(t[lc].thi>=x){
return rank(lc,cl,mid,x);
}else{
return rank(rc,mid+1,cr,x-t[lc].thi);
}
}
void modify(int& k,int l,int r,int cl,int cr,int x){
if(k==0){
k=++tot;
in_it(k);
}
if(l<=cl&&r>=cr){
t[k].tag=x;
t[k].thi=x*(cr-cl+1);
return;
}
int mid=(cl+cr)>>1;
push_down(k,cl,cr);
if(mid>=l){
modify(t[k].lef,l,r,cl,mid,x);
}
if(mid+1<=r){
modify(t[k].rig,l,r,mid+1,cr,x);
}
t[k]=merge(t[t[k].lef],t[t[k].rig],t[k]);
}
}tr;
struct disjoint_set{
int fa[N];
void _init(){
for(int i=0;i<=N-11;i++){
fa[i]=i;
}
}
int find(int x){
if(fa[x]!=x){
fa[x]=find(fa[x]);
}
return fa[x];
}
bool make(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx==fy){
return 0;
}
fa[fy]=fx;
return 1;
}
}st;
signed main(){
st._init();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a_[a[i]]=i;
tr._init(i);
tr.modify(tr.ver[i],a[i],a[i],1,n,1);
}
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
x=st.find(x);
y=st.find(y);
if(x==y){
continue;
}
st.make(x,y);
tr.make(tr.ver[x],tr.ver[y],1,n);
}
int k;
scanf("%d",&k);
while(k--){
char op;
cin>>op;
if(op=='Q'){
int x,y;
scanf("%d%d",&x,&y);
x=st.find(x);
int ans=tr.rank(tr.ver[x],1,n,y);
printf("%d\n",ans==-1?ans:a_[ans]);
}else{
int x,y;
scanf("%d%d",&x,&y);
x=st.find(x);
y=st.find(y);
if(x==y){
continue;
}
st.make(x,y);
tr.make(tr.ver[x],tr.ver[y],1,n);
}
}
return 0;
}线段树分裂
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=6.4e6+111;
struct pai{
int thi,tag,lef,rig;
};
int n,m;
int a[N];
struct tree{
pai t[N];
int tot=0,grd=0;
int ver[N];
void in_it(int x){
t[x]={0,0,0,0};
}
void _init(int grd){
tot++;
ver[grd]=tot;
in_it(tot);
}
int _merge(int a,int b){
return a+b;
}
pai merge(pai a,pai b,pai c){
pai ret{_merge(a.thi,b.thi),0,c.lef,c.rig};
return ret;
}
void push_down(int k,int cl,int cr){
if(t[k].tag==0){
return;
}
if(t[k].lef==0){
t[k].lef=++tot;
in_it(t[k].lef);
}
if(t[k].rig==0){
t[k].rig=++tot;
in_it(t[k].rig);
}
int lc=t[k].lef,rc=t[k].rig;
int mid=(cl+cr)>>1;
t[lc].tag+=t[k].tag;
t[rc].tag+=t[k].tag;
t[lc].thi+=t[k].tag*(mid-cl+1);
t[rc].thi+=t[k].tag*(cr-mid);
t[k].tag=0;
}
void kill(int &k,int &tp,int l,int r,int cl,int cr){
if(cr<l||cl>r||k==0){
return;
}
if(cl>=l&&cr<=r){
tp=k;
k=0;
return;
}
if(tp==0){
tp=++tot;
in_it(tp);
}
int mid=(cl+cr)>>1;
int lc=t[k].lef,rc=t[k].rig;
int ltc=t[tp].lef,rtc=t[tp].rig;
if(mid>=l){
kill(t[k].lef,t[tp].lef,l,r,cl,mid);
}
if(mid+1<=r){
kill(t[k].rig,t[tp].rig,l,r,mid+1,cr);
}
t[k]=merge(t[t[k].lef],t[t[k].rig],t[k]);
t[tp]=merge(t[t[tp].lef],t[t[tp].rig],t[tp]);
}
int make(int ka,int kb,int l,int r){
if(ka==0&&kb==0){
return 0;
}
if(ka==0){
// printf("|kb|id=%lld l=%lld r=%lld thi=%lld\n",kb,l,r,t[kb].thi);
return kb;
}
if(kb==0){
// printf("|ka|id=%lld l=%lld r=%lld thi=%lld\n",ka,l,r,t[ka].thi);
return ka;
}
if(l==r){
// printf("|kab|id=[%lld,%lld] l=%lld r=%lld|ll=%lld rr=%lld\n",ka,kb,l,r,t[ka].thi,t[kb].thi);
t[ka].thi=_merge(t[ka].thi,t[kb].thi);
return ka;
}
push_down(ka,l,r);
push_down(kb,l,r);
int mid=(l+r)/2;
t[ka].lef=make(t[ka].lef,t[kb].lef,l,mid);
t[ka].rig=make(t[ka].rig,t[kb].rig,mid+1,r);
t[ka]=merge(t[t[ka].lef],t[t[ka].rig],t[ka]);
// printf("|%lld|%lld %lld|l=%lld r=%lld thi=%lld\n",ka,l,r,t[ka].lef,t[ka].rig,t[ka].thi);
return ka;
}
int qry(int k,int l,int r,int cl,int cr){
if(k==0){
return 0;
}
if(cl>=l&&cr<=r){
return t[k].thi;
}
int mid=(cl+cr)>>1;
push_down(k,cl,cr);
int lc=t[k].lef,rc=t[k].rig;
int ansl=0,ansr=0;
if(mid>=l){
ansl=qry(lc,l,r,cl,mid);
}
if(mid+1<=r){
ansr=qry(rc,l,r,mid+1,cr);
}
return _merge(ansl,ansr);
}
int rank(int k,int cl,int cr,int x){
if(k==0){
return -1;
}
if(cl==cr){
return cl;
}
int mid=(cl+cr)>>1;
push_down(k,cl,cr);
int lc=t[k].lef,rc=t[k].rig;
// printf("||%lld|%lld %lld|l=%lld r=%lld|ll=%lld rr=%lld x=%lld\n",k,cl,cr,lc,rc,t[lc].thi,t[rc].thi,x);
if(t[lc].thi>=x){
return rank(lc,cl,mid,x);
}else{
return rank(rc,mid+1,cr,x-t[lc].thi);
}
}
void modify(int& k,int l,int r,int cl,int cr,int x){
if(k==0){
k=++tot;
in_it(k);
}
if(l<=cl&&r>=cr){
t[k].tag+=x;
t[k].thi+=x*(cr-cl+1);
return;
}
int mid=(cl+cr)>>1;
push_down(k,cl,cr);
if(mid>=l){
modify(t[k].lef,l,r,cl,mid,x);
}
if(mid+1<=r){
modify(t[k].rig,l,r,mid+1,cr,x);
}
t[k]=merge(t[t[k].lef],t[t[k].rig],t[k]);
}
}tr;
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
tr._init(i);
}
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
tr.modify(tr.ver[1],i,i,1,n,a[i]);
}
int top=1;
while(m--){
int op;
scanf("%lld",&op);
if(op==0){
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
tr.kill(tr.ver[x],tr.ver[++top],y,z,1,n);
}else if(op==1){
int x,y;
scanf("%lld%lld",&x,&y);
tr.ver[x]=tr.make(tr.ver[x],tr.ver[y],1,n);
}else if(op==2){
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
tr.modify(tr.ver[x],z,z,1,n,y);
}else if(op==3){
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
printf("%lld\n",tr.qry(tr.ver[x],y,z,1,n));
}else if(op==4){
int x,y;
scanf("%lld%lld",&x,&y);
int ans=tr.rank(tr.ver[x],1,n,y);
printf("%lld\n",ans);
}
}
return 0;
}多合一快读
#include <cctype>
#include <cstdio>
#include <cstring>
#include <string>
#include <type_traits>
#include <iostream>
#include <iomanip>
#ifdef __SIZEOF_INT128__
using int128_t = __int128;
#endif
class FastReader {
private:
static const int SIZE = 1 << 16;
char buf[SIZE], *p = buf, *end = buf;
inline void refill() {
if (p == end) {
p = buf;
end = buf + fread(buf, 1, SIZE, stdin);
}
}
inline char getChar() {
refill();
return *p++;
}
inline void ungetChar() {
if (p > buf) p--;
}
// 跳过空白字符
inline void skipWhitespace() {
while (true) {
refill();
if (p == end) return;
char c = *p;
if (c != ' ' && c != '\n' && c != '\r' && c != '\t') break;
p++;
}
}
// 读取有符号整数
template<typename T>
void readSignedInt(T& x) {
skipWhitespace();
bool negative = false;
char ch = getChar();
if (ch == '-') {
negative = true;
ch = getChar();
} else if (ch == '+') {
ch = getChar();
}
x = 0;
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getChar();
}
if (!(ch >= '0' && ch <= '9')) {
ungetChar();
}
if (negative) x = -x;
}
// 读取无符号整数
template<typename T>
void readUnsignedInt(T& x) {
skipWhitespace();
char ch = getChar();
x = 0;
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getChar();
}
if (!(ch >= '0' && ch <= '9')) {
ungetChar();
}
}
// 读取bool类型
void readBool(bool& x) {
skipWhitespace();
char ch = getChar();
if (ch == '1') {
x = true;
} else if (ch == '0') {
x = false;
} else if (ch == 't') {
// 检查"true"
getChar(); // 跳过 't'
getChar(); // 跳过 'r'
getChar(); // 跳过 'u'
getChar(); // 跳过 'e'
x = true;
} else if (ch == 'f') {
// 检查"false"
getChar(); // 跳过 'f'
getChar(); // 跳过 'a'
getChar(); // 跳过 'l'
getChar(); // 跳过 's'
getChar(); // 跳过 'e'
x = false;
} else {
// 其他情况视为false
x = false;
}
}
// 读取char类型
void readChar(char& x) {
skipWhitespace();
x = getChar();
}
// 读取double类型
void readDouble(double& x) {
skipWhitespace();
x = 0.0;
char ch = getChar();
bool negative = false;
if (ch == '-') {
negative = true;
ch = getChar();
} else if (ch == '+') {
ch = getChar();
}
// 整数部分
while (ch >= '0' && ch <= '9') {
x = x * 10.0 + (ch - '0');
ch = getChar();
}
// 小数部分
if (ch == '.') {
ch = getChar();
double fraction = 1.0;
while (ch >= '0' && ch <= '9') {
fraction *= 0.1;
x += (ch - '0') * fraction;
ch = getChar();
}
}
// 科学计数法
if (ch == 'e' || ch == 'E') {
ch = getChar();
int expSign = 1;
if (ch == '-') {
expSign = -1;
ch = getChar();
} else if (ch == '+') {
ch = getChar();
}
int exponent = 0;
while (ch >= '0' && ch <= '9') {
exponent = exponent * 10 + (ch - '0');
ch = getChar();
}
// 计算10的exponent次方
double pow10 = 1.0;
while (exponent > 0) {
pow10 *= 10.0;
exponent--;
}
if (expSign == -1) x /= pow10;
else x *= pow10;
}
if (!(ch >= '0' && ch <= '9') && ch != '.' && ch != 'e' && ch != 'E' && ch != '+' && ch != '-') {
ungetChar();
}
if (negative) x = -x;
}
// 读取float类型
void readFloat(float& x) {
double tmp;
readDouble(tmp);
x = static_cast<float>(tmp);
}
// 读取字符串（单词）
void readStringWord(std::string& s) {
skipWhitespace();
s.clear();
char ch = getChar();
while (ch != ' ' && ch != '\n' && ch != '\r' && ch != '\t' && ch != EOF) {
s.push_back(ch);
ch = getChar();
}
if (ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t' || ch == EOF) {
ungetChar();
}
}
// 读取整行
void readStringLine(std::string& s) {
s.clear();
char ch = getChar();
while (ch != '\n' && ch != EOF) {
s.push_back(ch);
ch = getChar();
}
// 处理Windows换行符\r\n
if (ch == '\r') {
ch = getChar();
if (ch != '\n') {
ungetChar();
}
}
}
// 读取C风格字符串
void readCString(char* s) {
skipWhitespace();
char ch = getChar();
int i = 0;
while (ch != ' ' && ch != '\n' && ch != '\r' && ch != '\t' && ch != EOF) {
s[i++] = ch;
ch = getChar();
}
s[i] = '\0';
if (ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t' || ch == EOF) {
ungetChar();
}
}
#ifdef __SIZEOF_INT128__
// 读取__int128类型
void readInt128(int128_t& x) {
skipWhitespace();
bool negative = false;
char ch = getChar();
if (ch == '-') {
negative = true;
ch = getChar();
} else if (ch == '+') {
ch = getChar();
}
x = 0;
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getChar();
}
if (!(ch >= '0' && ch <= '9')) {
ungetChar();
}
if (negative) x = -x;
}
#endif
public:
// 统一的读取函数 - 通过简单的重载实现
FastReader& read(char& x) {
readChar(x);
return *this;
}
FastReader& read(short& x) {
readSignedInt(x);
return *this;
}
FastReader& read(int& x) {
readSignedInt(x);
return *this;
}
FastReader& read(long& x) {
readSignedInt(x);
return *this;
}
FastReader& read(long long& x) {
readSignedInt(x);
return *this;
}
FastReader& read(unsigned short& x) {
readUnsignedInt(x);
return *this;
}
FastReader& read(unsigned int& x) {
readUnsignedInt(x);
return *this;
}
FastReader& read(unsigned long& x) {
readUnsignedInt(x);
return *this;
}
FastReader& read(unsigned long long& x) {
readUnsignedInt(x);
return *this;
}
FastReader& read(bool& x) {
readBool(x);
return *this;
}
FastReader& read(float& x) {
readFloat(x);
return *this;
}
FastReader& read(double& x) {
readDouble(x);
return *this;
}
FastReader& read(std::string& x) {
readStringWord(x);
return *this;
}
FastReader& read(char* x) {
readCString(x);
return *this;
}
#ifdef __SIZEOF_INT128__
FastReader& read(int128_t& x) {
readInt128(x);
return *this;
}
#endif
// 读取整行的辅助类
class Line {
public:
std::string& str;
explicit Line(std::string& s) : str(s) {}
};
FastReader& read(Line line) {
readStringLine(line.str);
return *this;
}
// 重载>>运算符
template<typename T>
FastReader& operator>>(T& x) {
return read(x);
}
FastReader& operator>>(Line line) {
return read(line);
}
};
// 全局FastReader实例
FastReader fin;
// 统一的read函数 - 简单直接的实现
template<typename T>
void read(T& x) {
fin.read(x);
}
template<typename T, typename... Args>
void read(T& first, Args&... args) {
read(first);
read(args...);
}
// 读取整行的辅助函数
inline FastReader::Line readline(std::string& str) {
return FastReader::Line(str);
}
inline std::string readline() {
std::string str;
fin.read(readline(str));
return str;
}
int main() {
// 测试各种类型
char c;
short s;
int i;
long long ll;
double d;
bool b;
std::string word;
std::string line;
// 使用read函数读取多个参数
read(c, s, i, ll, d, b);
// 读取一个单词
read(word);
// 读取整行
line=readline();
std::cout << "char: " << c << "\n";
std::cout << "short: " << s << "\n";
std::cout << "int: " << i << "\n";
std::cout << "long long: " << ll << "\n";
std::cout << "double: " << std::fixed << std::setprecision(6) << d << "\n";
std::cout << "bool: " << std::boolalpha << b << "\n";
std::cout << "string (word): " << word << "\n";
std::cout << "string (line): " << line << "\n";
// 使用>>运算符
int x, y;
fin >> x >> y;
std::cout << "x: " << x << ", y: " << y << "\n";
// 读取C风格字符串
char buffer[100];
fin >> buffer;
std::cout << "C string: " << buffer << "\n";
// 测试__int128（如果支持）
#ifdef __SIZEOF_INT128__
int128_t sdfgi128;
fin >> sdfgi128;
std::cout << "__int128: " << (long long)(sdfgi128 % 1000000000) << "...\n";
#endif
return 0;
}树链剖分
#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod;
const int N=2e5;
int n,m,begi;
int a[N],b[N];
vector<int>g[N];
struct tree{
struct pai{
long long thi,tag;
};
pai t[N<<2];
int _merge(int a,int b){
return (a+b)%mod;
}
pai merge(pai a,pai b){
pai ret{_merge(a.thi,b.thi),0};
return ret;
}
void push_down(int k,int cl,int cr){
if(t[k].tag==0){
return;
}
int lc=k<<1,rc=lc+1;
int mid=(cl+cr)>>1;
(t[lc].tag+=t[k].tag)%=mod;
(t[rc].tag+=t[k].tag)%=mod;
(t[lc].thi+=(mid-cl+1)*t[k].tag)%=mod;
(t[rc].thi+=(cr-mid)*t[k].tag)%=mod;
t[k].tag=0;
}
void build(int a[],int k,int cl,int cr){
if(cl==cr){
t[k].thi=a[cl];
return;
}
int lc=k<<1,rc=lc+1;
int mid=(cl+cr)>>1;
build(a,lc,cl,mid);
build(a,rc,mid+1,cr);
t[k]=merge(t[lc],t[rc]);
}
void init(int a[]){
build(a,1,1,n);
}
long long qry(int k,int l,int r,int cl,int cr){
if(cl>r||cr<l||l>r){
return 0;
}
if(cl>=l&&cr<=r){
return t[k].thi%mod;
}
int lc=k<<1,rc=lc+1;
int mid=(cl+cr)>>1;
push_down(k,cl,cr);
return _merge(qry(lc,l,r,cl,mid),qry(rc,l,r,mid+1,cr));
}
void modify(int k,int l,int r,int cl,int cr,long long x){
if(cl>r||cr<l||l>r){
return;
}
if(l<=cl&&r>=cr){
(t[k].tag+=x)%=mod;
(t[k].thi+=x*1ll*(cr-cl+1)%mod)%=mod;
return;
}
int lc=k<<1,rc=lc+1;
int mid=(cl+cr)>>1;
push_down(k,cl,cr);
modify(lc,l,r,cl,mid,x);
modify(rc,l,r,mid+1,cr,x);
t[k]=merge(t[lc],t[rc]);
}
}tr;
int tp[N],son[N],dfn[N];
int siz[N],dep[N],fa[N];
int tot;
void dfs1(int u,int dad){
dep[u]=dep[dad]+1;
siz[u]=1;
fa[u]=dad;
int maxx=-1,maxi=-1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v==dad){
continue;
}
dfs1(v,u);
if(siz[v]>maxx){
maxi=v;
maxx=siz[v];
}
siz[u]+=siz[v];
}
son[u]=maxi;
}
void dfs2(int u,int dad,int top){
dfn[u]=++tot;
tp[u]=top;
if(son[u]!=-1){
dfs2(son[u],u,top);
}
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v==dad||v==son[u]){
continue;
}
dfs2(v,u,v);
}
}
int qrylist(int x,int y){
int ans=0;
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]){
swap(x,y);
}
ans+=tr.qry(1,dfn[tp[x]],dfn[x],1,n);
ans%=mod;
x=fa[tp[x]];
}
if(dfn[x]>dfn[y]){
swap(x,y);
}
ans+=tr.qry(1,dfn[x],dfn[y],1,n);
ans%=mod;
return ans;
}
void modilist(int x,int y,int z){
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]){
swap(x,y);
}
tr.modify(1,dfn[tp[x]],dfn[x],1,n,z%mod);
x=fa[tp[x]];
}
if(dfn[x]>dfn[y]){
swap(x,y);
}
tr.modify(1,dfn[x],dfn[y],1,n,z%mod);
}
int qrytree(int x){
return tr.qry(1,dfn[x],dfn[x]+siz[x]-1,1,n);
}
void moditree(int x,int y){
tr.modify(1,dfn[x],dfn[x]+siz[x]-1,1,n,y%mod);
}
signed main(){
scanf("%lld%lld%lld%lld",&n,&m,&begi,&mod);
for(int i=1;i<=n;i++){
scanf("%lld",&b[i]);
}
for(int i=1;i<n;i++){
int x,y;
scanf("%lld%lld",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs1(begi,0);
dfs2(begi,0,begi);
for(int i=1;i<=n;i++){
a[dfn[i]]=b[i];
}
tr.init(a);
while(m--){
int op;
scanf("%lld",&op);
if(op==1){
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
modilist(x,y,z);
}else if(op==2){
int x,y;
scanf("%lld%lld",&x,&y);
printf("%lld\n",qrylist(x,y));
}else if(op==3){
int x,y;
scanf("%lld%lld",&x,&y);
moditree(x,y);
}else{
int x;
scanf("%lld",&x);
printf("%lld\n",qrytree(x));
}
}
return 0;
}treap/splay/FHQ-treap大合集
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+111;
int n;
struct Splay{
#define ll s[0]
#define rr s[1]
int root,tot=0;
struct tree{
int s[3];
int thi,fa,siz,t;
}tr[N];
bool right(int u){
return tr[tr[u].fa].rr==u;
}
void init(int u,int x,int fa){
tr[u].thi=x;
tr[u].fa=fa;
tr[u].siz=tr[u].t=1;
}
void merge(int u){
tr[u].siz=tr[tr[u].ll].siz+tr[tr[u].rr].siz+tr[u].t;
}
void flyup(int u){
int y=tr[u].fa;
int w=tr[y].fa;
bool nokx=right(u);
bool noky=right(y);
tr[w].s[noky]=u;
tr[u].fa=w;
tr[y].s[nokx]=tr[u].s[nokx^1];
tr[tr[u].s[nokx^1]].fa=y;
tr[u].s[nokx^1]=y;
tr[y].fa=u;
merge(y);
merge(u);
}
void splay(int u,int to){
while(tr[u].fa!=to){
int y=tr[u].fa;
int w=tr[y].fa;
if(w!=to){
if(right(u)!=right(y)){
flyup(u);
}else{
flyup(y);
}
}
flyup(u);
}
if(to==0){
root=u;
}
}
void find(int x){
int u=root;
if(u==0){
return;
}
while(tr[u].thi!=x&&tr[u].s[tr[u].thi<x]!=0){
u=tr[u].s[tr[u].thi<x];
}
splay(u,0);
}
void add(int x){
int u=root,fa=0;
while(u!=0&&tr[u].thi!=x){
fa=u;
u=tr[u].s[tr[u].thi<x];
}
if(u!=0){
tr[u].t++;
splay(u,0);
return;
}
u=++tot;
init(u,x,fa);
if(fa!=0){
tr[fa].s[tr[fa].thi<x]=u;
}
splay(u,0);
}
int prext(int x,bool f){
find(x);
int u=root;
if(f==0&&tr[u].thi<x){
return u;
}
if(f==1&&tr[u].thi>x){
return u;
}
u=tr[u].s[f];
while(tr[u].s[f^1]!=0){
u=tr[u].s[f^1];
}
splay(u,0);
return u;
}
void del(int x){
int l=prext(x,0);
int r=prext(x,1);
splay(l,0);
splay(r,l);
if(tr[tr[r].ll].t>1){
tr[tr[r].ll].t--;
splay(tr[r].ll,0);
return;
}
tr[r].ll=0;
merge(r);
merge(l);
}
int rank(int u){
add(u);
find(u);
int k=tr[tr[root].ll].siz;
del(u);
return k;
}
int rankth(int th){
th++;
int u=root;
if(tr[u].siz<th){
return -1;
}
while(1){
if(th>tr[tr[u].ll].siz+tr[u].t){
th-=tr[tr[u].ll].siz+tr[u].t;
u=tr[u].rr;
}else if(th<=tr[tr[u].ll].siz){
u=tr[u].ll;
}else{
splay(u,0);
return tr[u].thi;
}
}
}
void _init(){
add(-0x3f3f3f3f);
add(0x3f3f3f3f);
}
#undef ll
#undef rr
};
struct treap{
#define ll s[0]
#define rr s[1]
int root=0,tot=0;
struct tree{
int s[3];
int thi,siz,t,pri;
}tr[N];
int init(int x){
tr[tot].ll=tr[++tot].rr=0;
tr[tot].thi=x;
tr[tot].siz=tr[tot].t=1;
tr[tot].pri=rand();
return tot;
}
void merge(int u){
if(u==0){
return;
}
tr[u].siz=tr[tr[u].ll].siz+tr[tr[u].rr].siz+tr[u].t;
}
int zag(int u){
int v=tr[u].rr;
tr[u].rr=tr[v].ll;
tr[v].ll=u;
merge(u);
merge(v);
return v;
}
int zig(int u){
int v=tr[u].ll;
tr[u].ll=tr[v].rr;
tr[v].rr=u;
merge(u);
merge(v);
return v;
}
int add(int u,int x){
if(!u){
return init(x);
}
if(tr[u].thi==x){
tr[u].t++;
}else if(x<tr[u].thi){
tr[u].ll=add(tr[u].ll,x);
if(tr[tr[u].ll].pri>tr[u].pri){
u=zig(u);
}
}else if(x>tr[u].thi){
tr[u].rr=add(tr[u].rr,x);
if(tr[tr[u].rr].pri>tr[u].pri){
u=zag(u);
}
}
merge(u);
return u;
}
int del(int u,int x){
if(!u){
return 0;
}
if(tr[u].thi==x){
if(tr[u].t>1){
tr[u].t--;
}else{
if(!tr[u].ll&&!tr[u].rr){
return 0;
}
if(!tr[u].ll){
u=tr[u].rr;
}else if(!tr[u].rr){
u=tr[u].ll;
}else{
if(tr[tr[u].ll].pri>tr[tr[u].rr].pri){
u=zig(u);
tr[u].rr=del(tr[u].rr,x);
}else{
u=zag(u);
tr[u].ll=del(tr[u].ll,x);
}
}
}
}else if(x<tr[u].thi){
tr[u].ll=del(tr[u].ll,x);
}else{
tr[u].rr=del(tr[u].rr,x);
}
merge(u);
return u;
}
int rank(int u,int x){
if(!u){
return 1;
}
if(tr[u].thi==x){
return tr[tr[u].ll].siz+1;
}else if(x<tr[u].thi){
return rank(tr[u].ll,x);
}else{
return rank(tr[u].rr,x)+tr[tr[u].ll].siz+tr[u].t;
}
}
int rankth(int u,int k){
if(!u){
return -0x3f3f3f3f3f3f3f3f;
}
if(k<=tr[tr[u].ll].siz){
return rankth(tr[u].ll,k);
}else if(k<=tr[tr[u].ll].siz+tr[u].t){
return tr[u].thi;
}else{
return rankth(tr[u].rr,k-(tr[tr[u].ll].siz+tr[u].t));
}
}
int prext(int u,int x,bool f){
if(!u){
return f?0x3f3f3f3f3f3f3f3f:-0x3f3f3f3f3f3f3f3f;
}
if(f==0){
if(x<=tr[u].thi){
return prext(tr[u].ll,x,f);
}else{
return max(prext(tr[u].rr,x,f),tr[u].thi);
}
}else{
if(x>=tr[u].thi){
return prext(tr[u].rr,x,f);
}else{
return min(prext(tr[u].ll,x,f),tr[u].thi);
}
}
}
void _init(){
srand(time(0));
root=add(root,-0x3f3f3f3f3f3f3f3f);
root=add(root,0x3f3f3f3f3f3f3f3f);
}
#undef ll
#undef rr
};
struct fhq_treap{
#define ll s[0]
#define rr s[1]
int root=0,tot=0;
struct tree{
int s[3];
int thi,siz,t,pri;
}tr[N];
int init(int x){
tot++;
tr[tot].ll=tr[tot].rr=0;
tr[tot].thi=x;
tr[tot].siz=tr[tot].t=1;
tr[tot].pri=rand();
return tot;
}
void merge(int u){
if(u==0){
return;
}
tr[u].siz=tr[tr[u].ll].siz+tr[tr[u].rr].siz+tr[u].t;
}
pair<int,int> split(int u,int k){
if(!u){
return {0,0};
}
if(tr[u].thi<k){
pair<int,int> v=split(tr[u].rr,k);
tr[u].rr=v.first;
merge(u);
return {u,v.second};
}else{
pair<int,int> v=split(tr[u].ll,k);
tr[u].ll=v.second;
merge(u);
return {v.first,u};
}
}
int make(int u,int v){
if(!u||!v){
return max(u,v);
}
if(tr[u].pri<tr[v].pri){
tr[u].rr=make(tr[u].rr,v);
merge(u);
return u;
}else{
tr[v].ll=make(u,tr[v].ll);
merge(v);
return v;
}
}
void add(int x){
int u=init(x);
pair<int,int> v=split(root,x);
root=make(make(v.first,u),v.second);
}
void del(int x){
pair<int,int> a;
a=split(root,x);
pair<int,int> b;
b=split(a.second,x+1);
b.first=make(tr[b.first].ll,tr[b.first].rr);
root=make(a.first,make(b.first,b.second));
}
int rank(int u){
pair<int,int> v=split(root,u);
int k=tr[v.first].siz+1;
root=make(v.first,v.second);
return k;
}
int rankth(int u,int x){
if(x<=tr[tr[u].ll].siz){
return rankth(tr[u].ll,x);
}else if(x==tr[tr[u].ll].siz+1){
return tr[u].thi;
}else{
return rankth(tr[u].rr,x-(tr[tr[u].ll].siz+1));
}
}
int prext(int x,bool f){
if(!f){
return rankth(root,rank(x)-1);
}else{
return rankth(root,rank(x+1));
}
}
}t3;
signed main(){
scanf("%lld",&n);
while(n--){
int op,x;
scanf("%lld%lld",&op,&x);
if(op==1){
t3.add(x);
}else if(op==2){
t3.del(x);
}else if(op==3){
printf("%lld\n",t3.rank(x));
}else if(op==4){
printf("%lld\n",t3.rankth(t3.root,x));
}else if(op==5||op==6){
printf("%lld\n",t3.prext(x,op-5));
}
}
return 0;
}
神奇小哈希
struct custom_hash{
static uint64_t splitmix64(uint64_t x){
x+=0x9e3779b97f4a7c15;
x=(x^(x>>30))*0xbf58476d1ce4e5b9;
x=(x^(x>>27))*0x94d049bb133111eb;
return x^(x>>31);
}
size_t operator()(uint64_t x)const{
static const uint64_t FIXED_RANDOM=chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x+FIXED_RANDOM);
}
};