模板 #include<cstdio> using namespace std; const int N=100001; int n,tot,root,key[N],lefts[N],rights[N],size[N]; void Left_Rotate(int &x) { int y=rights[x]; rights[x]=lefts[y]; lefts[y]=x; size[y]=size[x]; size[x]=size[lefts[x]]+size[rights[x]]+1; x=y; } void Right_Rotate(int &x) { int y=lefts[x]; lefts[x]=rights[y]; rights[y]=x; size[y]=size[x]; size[x]=size[lefts[x]]+size[rights[x]]+1; x=y; } void Maintain(int &x,bool flag) { if(!flag) { if(size[lefts[lefts[x]]]>size[rights[x]]) Right_Rotate(x); else if(size[rights[lefts[x]]]>size[rights[x]]) Left_Rotate(lefts[x]),Right_Rotate(x); else return; } else { if(size[rights[rights[x]]]>size[lefts[x]]) Left_Rotate(x); else if(size[lefts[rights[x]]]>size[lefts[x]]) Right_Rotate(rights[x]),Left_Rotate(x); else return; } Maintain(lefts[x],0); Maintain(rights[x],1); Maintain(x,1); Maintain(x,0); } void Insert(int &x,int y) { if(!x) { x=++tot; key[x]=y; lefts[x]=rights[x]=0; size[x]=1; return; } size[x]++; if(y<=key[x]) Insert(lefts[x],y); else Insert(rights[x],y); Maintain(x,y>key[x]); } int Delete(int &x,int y) { size[x]--; if(y==key[x]||(y<key[x]&&!lefts[x])||(y>key[x]&&!rights[x])) { int ans=key[x]; if(!lefts[x]||!rights[x]) x=lefts[x]+rights[x]; else key[x]=Delete(lefts[x],key[x]+1); return ans; } if(y<key[x]) return Delete(lefts[x],y); else return Delete(rights[x],y); } bool Find(int &x,int y) { if(!x) return 0; if(y<=key[x]) return (y==key[x])||Find(lefts[x],y); else return Find(rights[x],y); } int Rank(int &x,int y) { if(!x) return 1; if(y<=key[x]) return Rank(lefts[x],y); else return size[lefts[x]]+1+Rank(rights[x],y); } int Select(int &x,int y) { if(y==size[lefts[x]]+1) return key[x]; if(y<=size[lefts[x]]) return Select(lefts[x],y); else return Select(rights[x],y-size[lefts[x]]-1); } int Pred(int &x,int y) { if(!x) return y; if(y<=key[x]) return Pred(lefts[x],y); else { int ans=Pred(rights[x],y); if(y==ans) return key[x]; else return ans; } } int Succ(int &x,int y) { if(!x) return y; if(y>=key[x]) return Succ(rights[x],y); else { int ans=Succ(lefts[x],y); if(y==ans) return key[x]; else return ans; } } void Inorder(int x) { if(x) { Inorder(lefts[x]); printf("%d ",key[x]); Inorder(rights[x]); } } int main() { freopen("sbt.in","r",stdin); scanf("%d",&n); for(int i=1,x,y;i<=n;i++) { scanf("%d%d",&x,&y); if(x==1) Insert(root,y); else if(x==2) Delete(root,y); else if(x==3) printf("%d\n",Find(root,y)); else if(x==4) printf("%d\n",Rank(root,y)); else if(x==5) printf("%d\n",Select(root,y)); else if(x==6) printf("%d\n",Pred(root,y)); else printf("%d\n",Succ(root,y)); Inorder(root);printf("\n\n"); } }
|
Delete:若不存在,删除后一个;若大于总数,删除最后一个
Rank:若不存在,返回后一个;若大于最大值,返回总数+1
Select:若大于总数,返回0
Pred:返回小于它的最大值;若小于最小值,返回本身
Succ:返回大于它的最小值;若大于最大值,返回本身
维护一些数,其中需要提供以下操作:
1.插入x数
2.删除x数(若有多个相同的数,因只删除一个)
3.查询x数的排名(若有多个相同的数,因输出最小的排名)
4.查询排名为x的数
5.求x的前驱(前驱定义为小于x,且最大的数)
6.求x的后继(后继定义为大于x,且最小的数)
太水了我就不贴代码了,基本和模板差不多
被遗弃的宠物过多时,来一个领养者特点值为a,那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。如果有两只满足要求的宠物,即存在两只宠物他们的特点值分别为a-b和a+b,那么领养者将会领养特点值为a-b的那只宠物。反之相同。
一个领养者领养了一个特点值为a的宠物,而它本身希望领养的宠物的特点值为b,那么这个领养者的不满意程度为abs(a-b)。求\(\sum min\lbrace abs(a-b)\rbrace\).
写主函数就好了,比较懒。。。
注意加上-inf和inf,不然两头的就会返回原值
然后把函数改一下,在前驱和后继里求的数就可以相同了 int Pred(int &x,int y) { if(!x) return inf; if(y<key[x]) return Pred(left[x],y); else { int ans=Pred(right[x],y); if(ans==inf) return key[x]; else return ans; } } int Succ(int &x,int y) { if(!x) return inf; if(y>key[x]) return Succ(right[x],y); else { int ans=Succ(left[x],y); if(ans==inf) return key[x]; else return ans; } } int main() { scanf("%d",&n); Insert(root,-inf);Insert(root,inf); for(int i=1,x,y;i<=n;i++) { scanf("%d%d",&x,&y); if(x==mark||!m) mark=x,m++,Insert(root,y); else { int a=Pred(root,y),b=Succ(root,y); if((long long)y-a<=(long long)b-y) ans=(ans+y-a)%mod,Delete(root,a); else ans=(ans+b-y)%mod,Delete(root,b); m--; } } printf("%d",ans); }
|
\[\sum_1^n min \lbrace abs(a[now]-a[pre]) \rbrace\]
注意如果之前存在值相同的点就不用再算了
或者把函数改成上一题的样子也行 int main() { scanf("%d",&n); Insert(root,-inf); Insert(root,inf); for(int i=1;i<=n;i++) { int x=0;scanf("%d",&x); if(i==1) ans+=x; else { int a=Pred(root,x),b=Succ(root,x); if((long long)x-a<=(long long)b-x) ans+=x-a; else ans+=b-x; } Insert(root,x); } printf("%d",ans); }
|
维护排名,分数大的在前,分数相同时先上传的在前。
支持:1、上传或修改;2、查询某个人的;3、查询某个区间
两个题一样,23333,一次A两个
但是坑爹呀,我写了两天,呜呜
因为同一个分数的有好多个,而再去查名字有点麻烦
所以就再记录一下时间,分数相同的人中时间是有序的
而且各种细节。。。慢慢调吧。。。
#include<cstring> #include<cstdio> #include<map> using namespace std; map<unsigned,int> m; const int N=250010; const int base=29; int n,root,tot,totnum,tottime,time[N]; int t[N],name[N],lefts[N],rights[N],size[N]; long long k[N],key[N]; char s[20],sname[N][11]; void Left_Rotate(int &x) { int y=rights[x]; rights[x]=lefts[y]; lefts[y]=x; size[y]=size[x]; size[x]=size[lefts[x]]+size[rights[x]]+1; x=y; } void Right_Rotate(int &x) { int y=lefts[x]; lefts[x]=rights[y]; rights[y]=x; size[y]=size[x]; size[x]=size[lefts[x]]+size[rights[x]]+1; x=y; } void Maintain(int &x,bool flag) { if(!flag) { if(size[lefts[lefts[x]]]>size[rights[x]]) Right_Rotate(x); else if(size[rights[lefts[x]]]>size[rights[x]]) Left_Rotate(lefts[x]),Right_Rotate(x); else return; } else { if(size[rights[rights[x]]]>size[lefts[x]]) Left_Rotate(x); else if(size[lefts[rights[x]]]>size[lefts[x]]) Right_Rotate(rights[x]),Left_Rotate(x); else return; } Maintain(lefts[x],0); Maintain(rights[x],1); Maintain(x,1); Maintain(x,0); } int Rank(int &x,int y,long long v) { if(!x) return 0; if(v==k[x]) { if(y==t[x]) return size[lefts[x]]+1; else if(y<t[x]) return Rank(lefts[x],y,v); else return size[lefts[x]]+1+Rank(rights[x],y,v); } if(v>k[x]) return Rank(lefts[x],y,v); else return size[lefts[x]]+1+Rank(rights[x],y,v); } int Findrank(int &x,int y) { if(y==size[lefts[x]]+1) return name[x]; if(y<=size[lefts[x]]) return Findrank(lefts[x],y); else return Findrank(rights[x],y-size[lefts[x]]-1); } void Insert(int &x,int y,long long v) { if(!x) { x=++tot; k[x]=v;t[x]=time[y];name[x]=y; lefts[x]=rights[x]=0; size[x]=1; return; } size[x]++; if(v>k[x]) Insert(lefts[x],y,v); else Insert(rights[x],y,v); Maintain(x,v<=k[x]); } void Delete(int &x,int y,long long v) { if((v>k[x]&&!lefts[x])||(v<k[x]&&!rights[x])) return; size[x]--; if(v==k[x]) { if(y==t[x]) { int ans=k[x]; if(!lefts[x]||!rights[x]) x=lefts[x]+rights[x]; else { int u=lefts[x]; while(rights[u]) u=rights[u]; k[x]=k[u];name[x]=name[u];t[x]=t[u]; Delete(lefts[x],t[u],k[u]); } return; } else if(y<t[x]) return Delete(lefts[x],y,v); else return Delete(rights[x],y,v); } if(v>k[x]) return Delete(lefts[x],y,v); else return Delete(rights[x],y,v); } int main() { freopen("rank.in","r",stdin); freopen("rank.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",s); if(s[1]>'9'||s[1]<'0') { unsigned a=0; for(int i=1;i<strlen(s);i++) a=a*base+s[i]-'A'+1; if(s[0]=='+') { long long j;scanf("%lld",&j); if(!m[a]) { m[a]=++totnum; for(int i=1;i<strlen(s);i++) sname[totnum][i-1]=s[i]; } else Delete(root,time[m[a]],key[m[a]]); key[m[a]]=j;time[m[a]]=++tottime; Insert(root,m[a],j); } else { if(!m[a]) printf("0\n"); else printf("%d\n",Rank(root,time[m[a]],key[m[a]])); } } else { int a=0; for(int i=1;i<strlen(s);i++) a=a*10+s[i]-'0'; for(int i=a;i<=a+9&&i<=size[root];i++) { int j=Findrank(root,i); if(i!=a) printf(" "); printf("%s",sname[j]); } printf("\n"); } } }
|

好像还比较水
注意立刻离开公司意味着不算进总人数
#include<cstdio> using namespace std; int n,minn,k,tot,root,ans; int key[100001],left[100001],right[100001],size[100001]; char s[1]; void Left_Rotate(int &x) { int y=right[x]; right[x]=left[y]; left[y]=x; size[y]=size[x]; size[x]=size[left[x]]+size[right[x]]+1; x=y; } void Right_Rotate(int &x) { int y=left[x]; left[x]=right[y]; right[y]=x; size[y]=size[x]; size[x]=size[left[x]]+size[right[x]]+1; x=y; } void Maintain(int &x,bool flag) { if(!flag) { if(size[left[left[x]]]>size[right[x]]) Right_Rotate(x); else if(size[right[left[x]]]>size[right[x]]) Left_Rotate(left[x]),Right_Rotate(x); else return; } else { if(size[right[right[x]]]>size[left[x]]) Left_Rotate(x); else if(size[left[right[x]]]>size[left[x]]) Right_Rotate(right[x]),Left_Rotate(x); else return; } Maintain(left[x],0); Maintain(right[x],1); Maintain(x,1); Maintain(x,0); } int Select(int &x,int y) { if(y==size[left[x]]+1) return key[x]; if(y<=size[left[x]]) return Select(left[x],y); else return Select(right[x],y-size[left[x]]-1); } void Insert(int &x,int y) { if(!x) { x=++tot; key[x]=y; left[x]=right[x]=0; size[x]=1; return; } size[x]++; if(y>=key[x]) Insert(left[x],y); else Insert(right[x],y); Maintain(x,y<key[x]); } int Delete(int &x,int y) { size[x]--; if((y>key[x]&&!left[x])||(y<key[x]&&!right[x])) return 0; if(y==key[x]) { int ans=key[x]; if(!left[x]||!right[x]) x=left[x]+right[x]; else { int t=Select(left[x],size[left[x]]); key[x]=Delete(left[x],t); } return ans; } if(y>key[x]) return Delete(left[x],y); else return Delete(right[x],y); } void Add(int &x,int y) { if(!x) return; Add(left[x],y); key[x]+=y; Add(right[x],y); } void Search(int &x) { if(!x) return; Search(left[x]);Search(right[x]); if(key[x]<minn) ans++,Delete(root,key[x]); } int main() { freopen("cashier.in","r",stdin); freopen("cashier.out","w",stdout); scanf("%d%d",&n,&minn); for(int i=1;i<=n;i++) { scanf("%s%d",s,&k); if(s[0]=='I') {if(k>=minn) Insert(root,k);} else if(s[0]=='A') Add(root,k),Search(root); else if(s[0]=='S') Add(root,-k),Search(root); else if(k>size[root]) printf("-1\n"); else printf("%d\n",Select(root,k)); } printf("%d\n",ans); }
|
给出N个数,要求把其中重复的去掉,只保留第一次出现的数。
太水了吧
set和map真好写,就是慢了点
其实SBT和它们的时间几乎没有差别。。。
才开始PE好几回,因为每行最后每空格。。。
int main() { scanf("%d",&T); while(T--) { scanf("%d",&n);tot=0;root=0; for(int i=1,x;i<=n;i++) { scanf("%d",&x); if(!Find(root,x)) { Insert(root,x); if(i>1) printf(" "); printf("%d",x); } } printf("\n"); } }
|
给定一个序列,初始为空。现在我们将1到N的数字插入到序列中,每次将一个数字插入到一个特定的位置。每插入一个数字,我们都想知道此时最长上升子序列长度是多少?
用平衡树先把序列求出来,然后用nlogn的算法求LIS(因为\(n^2\)过不了)
LIS:
法1:详解+演示
法2:原本的LIS是f[j]=f[i]+i (i<j&&h[i]<h[j])
用树状数组在logn时间内求出高度<h[j]的最大f值
#include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int N=100001; int n,tot,root,len; int f[N],a[N],ans[N],key[N],left[N],right[N],size[N]; void Left_Rotate(int &x) { int y=right[x]; right[x]=left[y]; left[y]=x; size[y]=size[x]; size[x]=size[left[x]]+size[right[x]]+1; x=y; } void Right_Rotate(int &x) { int y=left[x]; left[x]=right[y]; right[y]=x; size[y]=size[x]; size[x]=size[left[x]]+size[right[x]]+1; x=y; } void Maintain(int &x,bool flag) { if(!flag) { if(size[left[left[x]]]>size[right[x]]) Right_Rotate(x); else if(size[right[left[x]]]>size[right[x]]) Left_Rotate(left[x]),Right_Rotate(x); else return; } else { if(size[right[right[x]]]>size[left[x]]) Left_Rotate(x); else if(size[left[right[x]]]>size[left[x]]) Right_Rotate(right[x]),Left_Rotate(x); else return; } Maintain(left[x],0); Maintain(right[x],1); Maintain(x,1); Maintain(x,0); } void Insert(int &x,int y) { if(!x) { x=++tot; size[x]=1; return; } size[x]++; if(y<=size[left[x]]) Insert(left[x],y); else Insert(right[x],y-size[left[x]]-1); Maintain(x,y>key[x]); } void Inorder(int x) { if(x) { Inorder(left[x]); a[++tot]=x; Inorder(right[x]); } } int main() { scanf("%d",&n); for(int i=1,j;i<=n;i++) scanf("%d",&j),Insert(root,j); tot=0;Inorder(root); memset(f,127,sizeof(f)); f[0]=-0x7fffffff; for(int i=1;i<=n;i++) { int t=upper_bound(f,f+len+1,a[i])-f; if(f[t-1]<=a[i]) { if(a[i]<f[t]) f[t]=a[i]; ans[a[i]]=t; if(t>len) len=t; } } for(int i=1;i<=n;i++) { if(ans[i-1]>ans[i]) ans[i]=ans[i-1]; printf("%d\n",ans[i]); } }
|
法2例题:【COGS 2049】疯狂动物城
> 1.物理学要求:为了稳定和美观,半径大的蛋糕必须在放在半径小的蛋糕下面。
2.Mr.Big的钦定要求:编号小的蛋糕必须放在编号大的蛋糕下面。
你需要帮他制定一个使多层蛋糕总体积最大的方案。
注意:两个半径相同的蛋糕不能放在一起
#include<algorithm> #include<iostream> #include<cstdio> #include<cmath> using namespace std; const int N=100001; const double pi=3.14159265358979323846; int n,pos[N]; double ans,f,v[N],mx[N]; pair<int,int> a[N]; inline void Change(int x,double y) { for(;x<=n;x+=x&(-x)) mx[x]=max(mx[x],y); } inline double Quary(int x) { double maxx=0; for(;x;x-=x&(-x)) maxx=max(maxx,mx[x]); return maxx; } int main() { freopen("zootopia.in","r",stdin); freopen("zootopia.out","w",stdout); scanf("%d",&n); for(int i=n,x,y;i;i--) { scanf("%d%d",&x,&y); a[i]=make_pair(x,i); v[i]=pi*x*x*y; } sort(a+1,a+n+1); pos[a[1].second]=1; for(int i=2;i<=n;i++) pos[a[i].second]=pos[a[i-1].second]+(a[i].first!=a[i-1].first); for(int i=1;i<=n;i++) { f=Quary(pos[i]-1)+v[i]; Change(pos[i],f); ans=max(ans,f); } printf("%.2lf\n",ans); }
|