模板 #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);
}
|