~~所以您为什么粘下题解并提交~~
by twelveZ @ 2020-02-19 19:30:05
@[code_universe](/user/107232) 在本地跑的,没提交题解
by 光明正大 @ 2020-02-19 19:30:57
我在本地试了好多题解,发现好像输出都不对...
by 光明正大 @ 2020-02-19 19:31:31
@[光明正大](/user/121563) 我的程序里有一个上调/下调minn的操作,在操作‘A’跟 操作‘S’的时候
## Code:
```cpp
//good luck
# include <iostream>
# include <cstdio>
# include <cmath>
# include <cstdlib>
# include <cstring>
# include <string>
# include <algorithm>
# include <vector>
# include <queue>
# include <ctime>
# include <map>
#define LL long long
#define maxn int(1e6+5)
#define inf (int)1e9
#define is(a) (a>='0'&&a<='9')
#define iis(a) (a>='A'&&a<='Z')
#define iabs(a) ((a)>0?(a):(-a))
#define imax(a,b) ((a)>(b)?(a):(b))
#define imin(a,b) ((a)<(b)?(a):(b))
using namespace std;
struct data{int x,cnt,size,fa,ch[2];}t[maxn<<2];
int N,M,s,root,cntn,cnt,ans;
inline void reads(char &ch)
{
ch=getchar();
while (!iis(ch)) ch=getchar();
}
inline void read(int &x)
{
x=0;bool f=0;char ch=getchar();
for (;!is(ch);ch=getchar()) f|=ch=='-';
for (;is(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
x=f?-x:x;
}
inline int chk(int ro){return t[t[ro].fa].ch[1]==ro;}
inline void update(int ro){t[ro].size=t[t[ro].ch[0]].size+t[t[ro].ch[1]].size+t[ro].cnt;}
inline void rotate(int ro)
{
int x=t[ro].fa,w=chk(ro),wx=chk(x);
t[x].ch[w]=t[ro].ch[w^1]; t[t[ro].ch[w^1]].fa=x;
t[ro].fa=t[x].fa; t[ro].ch[w^1]=x;
t[t[x].fa].ch[wx]=ro; t[x].fa=ro;
update(x); update(ro);
}
inline void splay(int ro,int goal = 0)
{
while (t[ro].fa!=goal)
{
int x=t[ro].fa,y=t[x].fa;
if (y!=goal)
{
if (chk(ro)==chk(x)) rotate(x);
else rotate(ro);
}
rotate(ro);
}
if (!goal) root=ro;
}
inline void Insert(int x)
{
if (root==0) {++cntn;t[cntn].x=x;t[cntn].cnt=t[cntn].size=1;t[cntn].fa=0;t[cntn].ch[0]=t[cntn].ch[1]=0;root=1;return;}
int now=root,p=root;
while (now)
{
if (t[now].x==x) {++t[now].cnt;update(now);splay(now);return;}
p=now;
now=t[now].ch[x>t[now].x];
if (now==0) {++cntn;now=cntn;t[now].x=x;t[now].cnt=t[now].size=1;t[now].fa=p;t[now].ch[0]=t[now].ch[1]=0;t[p].ch[x>t[p].x]=now;update(p);splay(now);return;}
}
}
inline void find(int x)
{
if (!root) return;
int now=root;
while (t[now].ch[x>t[now].x]&&x!=t[now].x) now=t[now].ch[x>t[now].x];
splay(now);
}
inline int findx(int x)
{
int now=root;
while (now)
{
if (t[t[now].ch[1]].size>=x) now=t[now].ch[1];
else
{
x-=t[t[now].ch[1]].size;
if (x<=t[now].cnt) return t[now].x;
x-=t[now].cnt;
now=t[now].ch[0];
}
}
}
inline void del(int x)
{
find(x);
if (t[root].x>=x) {ans+=t[t[root].ch[0]].size-1;t[root].ch[0]=0;Insert(-2147483647);return;}
ans+=t[t[root].ch[0]].size+t[root].cnt-1;
root=t[root].ch[1];
t[root].fa=0;
Insert(-2147483647);
}
int main()
{
read(N);read(M);
Insert(2147483647);
Insert(-2147483647);
for (int i = 1; i <= N; ++i)
{
char ch;
int x;
reads(ch);read(x);
if (ch=='I')
{
if (x>=M+s) Insert(x-s),++cnt;
}
if (ch=='A') M-=x,s+=x;
if (ch=='S') M+=x,s-=x,del(M);
if (ch=='F') printf("%d\n",cnt-ans<x?-1:findx(x+1)+s);
}
printf("%d\n",ans);
return 0;
}
```
by formkiller @ 2020-02-19 20:02:47
@[formkiller](/user/186141)
我主要想用fhq-treap
不过还是谢谢您
最后我发现WA是因为最后一个else
后来写成这就过了
```cpp
while (n--) {
scanf("%s",opt);int k=read(),x,y;
if(opt[0]=='I'&&k>=minn) {
split(root,k-delta,x,y);//注意更新的是减去delta后的值
tr[++cnt].rnd=rand();tr[cnt].dat=k-delta;tr[cnt].size=1;
root=mergy(mergy(x,cnt),y);
}
else if(opt[0]=='A') delta+=k;//所有人都加上k
else if(opt[0]=='S') {
delta-=k;//所有人都减去k
split(root,minn-delta-1,x,y);//w+delta<minn<==>w<=minn-delta-1
sum+=tr[x].size;root=y;//直接扔掉左子树即可
}
else if(opt[0]=='F') //不要只写一个else啊!!!!!!!!!!!!
printf("%d\n",tr[root].size<k?-1:tr[kth(root,tr[root].size+1-k)].dat +delta);
}
```
by 光明正大 @ 2020-02-19 20:40:04