BZOJ 5110: [CodePlus2017]Yazid 的新生舞会 线段树

非常好的一道思维题.   

code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define lson x<<1
#define rson x<<1|1
#define N 500010
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
ll ans;
int n;
vector<int>p[N];
int s1[N<<3],z1[N<<3];
ll s2[N<<3],z2[N<<3];
int tag[N<<3];
bool clr[N<<3];
void pushdown(int x)
{
if(clr[x])
{
clr[lson]=clr[rson]=1,s1[lson]=s1[rson]=s2[lson]=s2[rson]=tag[lson]=tag[rson]=clr[x]=0;
}
if(tag[x])
{
s1[lson]+=z1[lson]*tag[x],s1[rson]+=z1[rson]*tag[x];
s2[lson]+=z2[lson]*tag[x],s2[rson]+=z2[rson]*tag[x];
tag[lson]+=tag[x],tag[rson]+=tag[x];
tag[x]=0;
}
}
void build(int l,int r,int x)
{
if(l==r)
{
z1[x]=1,z2[x]=l;
return;
}
int mid=(l+r)>>1;
build(l,mid,lson),build(mid+1,r,rson);
z1[x]=z1[lson]+z1[rson];
z2[x]=z2[lson]+z2[rson];
}
void update(int l,int r,int x,int L,int R)
{
if(l>=L&&r<=R)
{
s1[x]+=z1[x],s2[x]+=z2[x],++tag[x];
return;
}
pushdown(x);
int mid=(l+r)>>1;
if(L<=mid)
update(l,mid,lson,L,R);
if(R>mid)
update(mid+1,r,rson,L,R);
s1[x]=s1[lson]+s1[rson],s2[x]=s2[lson]+s2[rson];
}
int query1(int l,int r,int x,int L,int R)
{
if(l>=L&&r<=R) return s1[x];
pushdown(x);
int mid=(l+r)>>1,re=0;
if(L<=mid)
re+=query1(l,mid,lson,L,R);
if(R>mid)
re+=query1(mid+1,r,rson,L,R);
return re;
}
ll query2(int l,int r,int x,int L,int R)
{
if(l>=L&&r<=R) return s2[x];
pushdown(x);
int mid=(l+r)>>1;
ll re=0;
if(L<=mid)
re+=query2(l,mid,lson,L,R);
if(R>mid)
re+=query2(mid+1,r,rson,L,R);
return re;
}
int main()
{
// setIO("input");
scanf("%d",&n);
int yy; scanf("%d",&yy);
int i,j,l,r,sum;
for(i=1;i<=n;++i) scanf("%d",&j), p[j].push_back(i);
build(-n,n,1);
for(i=0;i<n;++i) if(p[i].size())
{
s1[1]=s2[1]=tag[1]=sum=0,clr[1]=1;
p[i].push_back(n+1);
update(-n,n,1,0,0);
for(j=0;j<p[i].size();++j)
{
if((!j&&p[i][j]>1)||(j&&p[i][j]>p[i][j-1]+1))
{
l=(!j)?1:(p[i][j-1]+1),r=p[i][j]-1;
if(j) ans+=query1(-n,n,1,-n,sum-1)*(r-l+1)-query2(-n,n,1,sum-(r-l+1),sum-1)+query1(-n,n,1,sum-(r-l+1),sum-1)*(sum-1-(r-l+1));
update(-n,n,1,sum-(r-l+1),sum-1);
sum-=(r-l+1);
}
if(j!=p[i].size()-1) ++sum,ans+=query1(-n,n,1,-n,sum-1),update(-n,n,1,sum,sum);
}
}
printf("%lldn",ans);
return 0;
}