```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;int cnt=0;
struct node{
int l,r,dis,f,val;
}t[1000010];
int add(int x)
{
t[++cnt].f=cnt;
t[cnt].val=x;
return cnt;
}
int find(int x)
{
if(t[x].f==x)return x;
return t[x].f=find(t[x].f);
}
int mer(int x,int y)
{
if(!x||!y)return x+y;
if(t[x].val<t[y].val||(t[x].val==t[y].val&&x>y))swap(x,y);
t[x].r=mer(t[x].r,y);
t[t[x].r].f=x;
if(t[t[x].l].dis<t[t[x].r].dis)swap(t[x].l,t[x].r);
t[x].dis=t[t[x].r].dis+1;
return x;
}
int n,m;
int main()
{
while(scanf("%d",&n)!=EOF)
{
t[0].dis=-1;
for(int i=1;i<=n;i++)
{
t[i].f=i;
t[i].l=0;
t[i].r=0;
t[i].dis=0;
scanf("%d",&t[i].val);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
int fx=find(x);
int fy=find(y);
if(fx==fy)
{
printf("-1\n");
continue;
}
else//加入两个最大的除以2
{
int rt;
t[fx].val/=2;t[fy].val/=2;
rt=mer(t[fx].l,t[fx].r);
t[fx].l=0;t[fx].r=0;t[fx].dis=0;
int rta=mer(rt,fx);
t[rt].f=t[fx].f=rta;
rt=mer(t[fy].l,t[fy].r);
t[fy].l=0;t[fy].r=0;t[fy].dis=0;
int rtb=mer(rt,fy);
t[rt].f=t[fy].f=rtb;
rt=mer(rta,rtb);
t[rta].f=t[rtb].f=rt;
printf("%d\n",t[rt].val);
}
}
}
return 0;
}
```
by GLZP @ 2019-02-18 17:40:10
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;int cnt=0;
int n,m;
int root;
struct node
{
int l,r,size,val,key;
}t[200010];
int hp[50010];
void add(int x)
{
t[++cnt].size=1;
t[cnt].val=x;
t[cnt].key=rand();
t[cnt].l=t[cnt].r=0;
}
void update(int u)
{
t[u].size=t[t[u].l].size+t[t[u].r].size+1;
}
int mer(int l,int r)
{
if(!l||!r)
return l+r;
if(t[l].key<t[r].key)
{
t[l].r=mer(t[l].r,r);
update(l);
return l;
}
else
{
t[r].l=mer(l,t[r].l);
update(r);
return r;
}
}
void split(int u,int x,int &l,int &r)
{
if(!u)
{
l=r=0;
return;
}
if(t[u].val<=x)
{
l=u;
split(t[u].r , x, t[u].r, r);
}
else
{
r=u;
split(t[u].l , x, l, t[u].l);
}
update(u);
}
int kth (int u,int k)
{
if(t[t[u].l].size+1==k)return u;
if(t[t[u].l].size+1>k)return kth(t[u].l,k);
else return kth(t[u].r,k-t[t[u].l].size-1);
}
int main()
{
int l,r,p;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&hp[i]);
split(root,hp[i],l,r);
add(hp[i]);
root=mer(mer(l,cnt),r);
}
scanf("%d",&m);
int tot=n;
for(int i=1;i<=m;i++)
{
char tpp;
int a,b;
scanf(" %c ",&tpp);
if(tpp=='A')//攻击，单点修改减
{
scanf("%d %d",&a,&b);
split(root,hp[a],l,r);
split(l,hp[a]-1,l,p);
int rt=mer(t[p].l,t[p].r);
root=mer(mer(l,rt),r);
t[p].val-=b;hp[a]-=b;
t[p].l=t[p].r=0;t[p].size=1;
if(hp[a]<=0)
{
tot--;
continue;
}
split(root,hp[a],l,r);
root=mer(mer(l,p),r);
}
else if(tpp=='C')
{//单点修改加
scanf("%d %d",&a,&b);
split(root,hp[a],l,r);
split(l,hp[a]-1,l,p);
int rt=mer(t[p].l,t[p].r);
root=mer(mer(l,rt),r);
t[p].val+=b;hp[a]+=b;
t[p].l=0;t[p].r=0;t[p].size=1;
split(root,hp[a],l,r);
root=mer(mer(l,p),r);
}
else
{
scanf("%d",&a);
if(a>tot)
{
printf("-1\n");
continue;
}
printf("%d\n",t[kth(root,tot-a+1)].val);
}
}
printf("%d\n",tot);
return 0;
}
```
by GLZP @ 2019-02-18 21:27:01
#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int M=3e5+10;
int n,q,t,ans,last;
int opt,x;
int cnt[M],born[M],die[M],belong[M];
//cnt表示信箱i的信的数量
//born表示第i封信放入的时间
//die表示信箱i取出的时间
//belong表示第i封信属于哪个信箱
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=q;i++){
scanf("%d%d",&opt,&x);
if(opt==1){
ans++;t++;
cnt[x]++;
born[t]=i;
belong[t]=x;
printf("%d\n",ans);
}
else if(opt==2){
ans-=cnt[x];
cnt[x]=0;
die[x]=i;
printf("%d\n",ans);
}
else{
if(x>last){
for(int j=last+1;j<=x;j++){
if(die[belong[j]]>born[j]) continue ;
ans--;
cnt[belong[j]]--;
}
last=x;
}
printf("%d\n",ans);
}
}
return 0;
}
by L______ @ 2019-04-02 08:51:30
```cpp
#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int M=3e5+10;
int n,q,t,ans,last;
int opt,x;
int cnt[M],born[M],die[M],belong[M];
//cnt表示信箱i的信的数量
//born表示第i封信放入的时间
//die表示信箱i取出的时间
//belong表示第i封信属于哪个信箱
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=q;i++){
scanf("%d%d",&opt,&x);
if(opt==1){
ans++;t++;
cnt[x]++;
born[t]=i;
belong[t]=x;
printf("%d\n",ans);
}
else if(opt==2){
ans-=cnt[x];
cnt[x]=0;
die[x]=i;
printf("%d\n",ans);
}
else{
if(x>last){
for(int j=last+1;j<=x;j++){
if(die[belong[j]]>born[j]) continue ;
ans--;
cnt[belong[j]]--;
}
last=x;
}
printf("%d\n",ans);
}
}
return 0;
}
```
by L______ @ 2019-04-02 08:54:14
```
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define re register
#define oo 0x7f7f7f7f
#define O_O 100005
using namespace std;
inline int read()
{
re int x=0,f=1;
re char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while('0'<=c&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int n,m,q;
int num[O_O*4];
int maxn,minn;
struct date
{
int l,r,opt;
}change[O_O];
inline int min(int a,int b) { return a<b?a:b; }
inline int max(int a,int b) { return a>b?a:b; }
namespace SEG
{
#define ls (u<<1)
#define rs (u<<1|1)
int sign[O_O*4],sum[O_O*4],len[O_O*4];
void build(int u,int l,int r,int k)
{
len[u]=r-l+1;
if(l==r)
{
sum[u]=num[l]>=k?1:0;
return ;
}
re int mid=(l+r)>>1;
build(ls,l,mid,k); build(rs,mid+1,r,k);
sum[u]=sum[ls]+sum[rs];
}
inline void spread(int u)
{
sign[ls]=sign[u];
sum[ls]=len[ls]*sign[u];
sign[rs]=sign[u];
sum[rs]=len[rs]*sign[u];
sign[u]=-1;
}
void modify(int u,int l,int r,int a,int b,int k)
{
if(a>b) return ;
if(a<=l&&r<=b)
{
sign[u]=k;
sum[u]=len[u]*k;
return ;
}
if(sign[u]!=-1) spread(u);
re int mid=(l+r)>>1;
if(mid>=b) modify(ls,l,mid,a,b,k);
else if(mid<a) modify(rs,mid+1,r,a,b,k);
else modify(ls,l,mid,a,mid,k),modify(rs,mid+1,r,mid+1,b,k);
sum[u]=sum[ls]+sum[rs];
}
int query(int u,int l,int r,int a,int b)
{
if(a>b) return 0;
if(a<=l&&r<=b) return sum[u];
if(sign[u]!=-1) spread(u);
re int mid=(l+r)>>1;
if(mid>=b) return query(ls,l,mid,a,b);
else if(mid<a) return query(rs,mid+1,r,a,b);
return query(ls,l,mid,a,mid)+query(rs,mid+1,r,mid+1,b);
}
}
using namespace SEG;
bool check(int lit)
{
// printf("%d\n",lit);
re int te,t1,t2;
memset(sign,-1,sizeof(sign));
build(1,1,n,lit);
for(re int i=1;i<=m;++i)
{
t1=change[i].l;
t2=change[i].r;
te=query(1,1,n,t1,t2);
if(change[i].opt)
{
modify(1,1,n,t1,t1+te-1,1);
modify(1,1,n,t1+te,t2,0);
}
else
{
modify(1,1,n,t1,t2-te,0);
modify(1,1,n,t2-te+1,t2,1);
}
}
return query(1,1,n,q,q);
}
signed main()
{
n=read();m=read();
for(re int i=1;i<=n;++i ) num[i]=read();
for(re int i=1;i<=m;++i)
{
change[i].opt=read();
change[i].l=read();
change[i].r=read();
}
q=read();
int l=1,r=n,midd,ans;
while(l<=r)
{
midd=(l+r)>>1;
if(check(midd)) l=midd+1,ans=midd;
else r=midd-1;
}
printf("%d",ans);
}
```
by 取名字好烦啊 @ 2019-10-02 19:26:50