题解 P3608 【[USACO17JAN]Balanced Photo平衡的照片】

2017-10-08 19:06:04


好久不打高级数据结构了

然后就打了个主席树

然后就a了

#include<bits/stdc++.h>
using namespace std;
int n,l[5000000],r[5000000],a[5000000],sum[5000000],x,y,ans,kk;
int putit(int x,int y,int z,int ll,int rr){//加入元素
    sum[x]=sum[y];if (ll==rr){sum[x]++;return x;}int m=(ll+rr)/2;
    if (z<=m){l[x]=putit(++kk,l[y],z,ll,m);r[x]=r[y];}
    if (z>m){r[x]=putit(++kk,r[y],z,m+1,rr);l[x]=l[y];}
    sum[x]=sum[l[x]]+sum[r[x]];return x;
}int findit(int x,int y,int z,int ll,int rr){//删除元素
    if (ll==z)return sum[y]-sum[x];
    int m=(ll+rr)/2;if (!y)return 0;
    if (z<=m)return sum[r[y]]-sum[r[x]]+findit(l[x],l[y],z,ll,m);
        else return findit(r[x],r[y],z,m+1,rr);
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n;kk=n;for (int i=1;i<=n;i++)cin>>a[i],putit(i,i-1,a[i],0,1e9);
    for (int i=1;i<=n;i++){
        x=findit(0,i-1,a[i]+1,0,1e9);y=findit(i,n,a[i]+1,0,1e9);if (x<y)swap(x,y);
                    //找出在i左边的比i大的元素和在i右边比i大的元素并且形成有序点对
        if (2*y<x)ans++;//这里题面翻译有误
    }cout<<ans<<endl;
}