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

好久不打高级数据结构了 然后就打了个主席树 然后就a了 ```cpp #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; } ```