破解密码

3s,512MB

题目背景

2058年，Alice奉命破解密码，然而密码实在是太美，所以Alice想先知道一下可能的密码的数量。

题目描述

具体的，密码由一个神秘人给出的集合得到。定义密码是一个整数 $x$ ，满足 $ \exists S,T,\ |S|=|T|,\ Sum(S)\leq x,\ Sum(T)\geq x+1 $ ，其中 $S,T$ 是包含于全集 $U$ 的集合。显然密码可能有多种，因此Alice关心有多少种不同的密码（定义 $|S|$ 表示集合 $S$ 的大小， $Sum(S)$ 表示集合内所有元素之和）。

不幸的是，这个集合年代久远，Alice记不清了，所以每次Alice会修改这个集合，具体的，Alice从集合中删去一个元素，或加入一个元素。每次修改之后，你需要帮助Alice求出可能密码的数量，即满足上述条件 $x$ 的数量。

输入格式

第一行整数 $n,q$ ，表示初始集合的大小，和Alice修改的次数。

第二行 $n$ 个整数描述初始集合。

接下来 $q$ 行，每行两个整数 $x,y$ ，若 $x=1$ 则加入 $y$ ，否则删除 $y$ ，输入保证合法。

输出格式

$q+1$ 行，表示所有修改前每次修改后的答案，即对于当前集合，满足上述所有条件的 $x$ 的数量。

样例1

1 7
5
1 6
0 6
1 9
1 7
0 5
0 9
0 7

0
1
0
4
8
2
0
0

数据范围

对于所有数据， $n,q\leq 2\times 10^5$ ， $\forall x \in [1,n],\ x\leq 10^{12}$ 。

保证无论何时若集合非空则元素两两不同。

#include<bits/stdc++.h>
#define file(x)freopen(x".in","r",stdin);freopen(x".out","w",stdout)
#define inf 1e13
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define re register ll
#define fr first
#define sd second
#define pa pair<ll,ll>
#define FOR(i,a,b) for(re i=a;i<=b;i++)
#define REP(i,a,b) for(re i=a;i>=b;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define N 200010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
inline ll lowbit(ll x){return x&(-x);}
struct node
{
	ll sum,LS,RS,num;// LS 鏄墠缂€鍜岋紝 RS 鏄悗缂€鍜?
}t[N*60];
node st[N];ll top=0;
int ls[N*60],rs[N*60];
ll n,q,tot;int rt;
ll a[N],x[N],op[N],p[N<<1],tmp;
#define mid ((l+r)>>1)
inline void pushup(ll x)
{
	t[x].num=t[ls[x]].num+t[rs[x]].num;
	t[x].sum=t[ls[x]].sum+t[rs[x]].sum;
	t[x].LS=t[ls[x]].LS+t[rs[x]].LS+t[rs[x]].num*t[ls[x]].sum;
	t[x].RS=t[ls[x]].RS+t[rs[x]].RS+t[ls[x]].num*t[rs[x]].sum; 
}
void add(ll l,ll r,int &x,ll pos,ll opt)
{
	if(!x)x=++tot;
	if(l==r)
	{
		if(opt>0){t[x].num=1;t[x].sum=t[x].LS=t[x].RS=p[l];}
		else {t[x].num=0;t[x].sum=t[x].LS=t[x].RS=0;}
		return ;
	}
	if(pos<=mid)add(l,mid,ls[x],pos,opt);
	else add(mid+1,r,rs[x],pos,opt);
	pushup(x);
}
ll qk(ll l,ll r,ll x,ll k,ll op,ll &s)// 璇㈤棶绗?k 灏忎笌鍓?k 灏忕殑鍜?鍓?k 澶т笌鍓?k 澶х殑鍜?
{
	if(l==r){s+=p[l];return l;}
	if(!op)
	{
		if(t[ls[x]].num>=k)return qk(l,mid,ls[x],k,op,s);
		else {s+=t[ls[x]].sum;return qk(mid+1,r,rs[x],k-t[ls[x]].num,op,s);}
	}
	else
	{
		if(t[rs[x]].num>=k)return qk(mid+1,r,rs[x],k,op,s);
		else {s+=t[rs[x]].sum;return qk(l,mid,ls[x],k-t[rs[x]].num,op,s);}
	}
}
void qry(ll l,ll r,ll x,ll ql,ll qr)//灏嗕竴涓尯闂寸殑绾挎鏍戣妭鐐瑰彇鍑?
{
	if(ql>qr||!x)return ;
	if(l==ql&&r==qr){st[++top]=t[x];return ;}
	if(qr<=mid)qry(l,mid,ls[x],ql,qr);
	else if(ql>mid)qry(mid+1,r,rs[x],ql,qr);
	else {qry(l,mid,ls[x],ql,mid);qry(mid+1,r,rs[x],mid+1,qr);}
}
inline ll QS(ll l,ll r)//璇㈤棶鍖洪棿鍜?
{
	top=0;qry(1,tmp,rt,l,r);
	ll s=0;FOR(i,1,top)s+=st[i].sum;
	return s;
}
inline ll qsum(ll l,ll r,ll op)//璇㈤棶鍖洪棿鍓嶇紑鍜?鍚庣紑鍜?
{
	top=0;qry(1,tmp,rt,l,r);
	ll s=0,ans=0;
	if(op==0){FOR(i,1,top){ans+=st[i].LS+s*st[i].num;s+=st[i].sum;}}
	if(op==1){REP(i,top,1){ans+=st[i].RS+s*st[i].num;s+=st[i].sum;}}
	return ans;
}
inline ll qans()
{
	if(n==0){return 0;}
	ll l=1,r=n-1,pl=0,pr=0;
	ll ans=0;
	while(l<=r)
	{
		ll s1=0,s2=0;
		ll R=qk(1,tmp,rt,mid+1,0,s1),L=qk(1,tmp,rt,mid,1,s2);
		if(s1<=s2)pl=mid,r=mid-1;
		else l=mid+1;
	}
	l=1,r=n-1;
	while(l<=r)
	{
		ll s1=0,s2=0;
		ll R=qk(1,tmp,rt,mid+1,0,s1),L=qk(1,tmp,rt,mid,1,s2);
		if(s1<=s2)pr=mid+1,l=mid+1;
		else r=mid-1;
	}
	if(pl==0){return qsum(1,tmp,1)-qsum(1,tmp,0);}
	if(pr<n)
	{
		ll s=0;
		ll L=qk(1,tmp,rt,pr+1,0,s),R=qk(1,tmp,rt,pr+1,1,s);
		ans+=qsum(1,R-1,1)+QS(R,tmp)*(n-pr);
		ans-=qsum(L+1,tmp,0)+QS(1,L)*(n-pr);
	}
	if(pl>1)
	{
		ll s=0;
		ll L=qk(1,tmp,rt,pl-1,0,s),R=qk(1,tmp,rt,pl-1,1,s);
		ans+=qsum(R,tmp,1);ans-=qsum(1,L,0);
	}
	ll s=0;
	ans-=QS(1,qk(1,tmp,rt,pl,0,s));ans+=QS(qk(1,tmp,rt,pr,1,s),tmp);
	return ans;
}
int main()
{
//	file("keyword");
	n=read(),q=read();
	FOR(i,1,n)a[i]=read(),p[++tmp]=a[i];
	FOR(i,1,q)op[i]=read(),x[i]=read(),p[++tmp]=x[i];
	sort(p+1,p+tmp+1);tmp=unique(p+1,p+tmp+1)-p-1;
	FOR(i,1,n)a[i]=lower_bound(p+1,p+tmp+1,a[i])-p;
	FOR(i,1,q)x[i]=lower_bound(p+1,p+tmp+1,x[i])-p;
	FOR(i,1,n)add(1,tmp,rt,a[i],1);
	cout<<qans()<<'\n';
	FOR(i,1,q)
	{
		ll opt=op[i],X=x[i];
		if(opt==1){add(1,tmp,rt,X,1);n++;}
		else {add(1,tmp,rt,X,-1);n--;}
		cout<<qans()<<'\n';
	}
	return 0;
}