题面传送门 首先有一个结论就是不存在二次变换。 如果存在二次变换，那么二次变换那个点的至少一个方向会新出现一个点，但是要新出现一个点那个方向必定原来就存在一个点。所以不成立。 那么就可以从上到下做扫描线，当碰到一列最上面的点时给树状数组那个位置加一，最下面减一就好了。 代码实现:
#include<cstdio> #include<vector> #include<cstring> #include<algorithm> #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; int n,m,k,longge,now,last,f[200039],x[100039],y[100039],z,nows[200039],tots[200039],l,r,mid,s1[200039],s2[200039],minn[200039],maxn[200039]; long long ans; vector<int> s[200039]; inline int ls(int x){ l=0;r=2*n+1; while(l+1<r){ mid=(l+r)>>1; if(nows[mid]<x) l=mid; else r=mid; } return tots[r]; } inline void get(int x,int y){while(x<=2*n) f[x]+=y,x+=x&-x;} inline int find(int x){int ans=0;while(x) ans+=f[x],x-=x&-x;return ans;} int main(){ // freopen("1.in","r",stdin); register int i,j; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]),nows[i*2-1]=x[i],nows[i*2]=y[i]; sort(nows+1,nows+2*n+1); nows[0]=nows[1]-1; for(i=1;i<=2*n;i++){ tots[i]=tots[i-1]; if(nows[i]!=nows[i-1]) tots[i]++; } memset(minn,0x3f,sizeof(minn)); memset(s1,0x3f,sizeof(s1)); for(i=1;i<=n;i++)x[i]=ls(x[i]),y[i]=ls(y[i]); for(i=1;i<=n;i++) s[x[i]].push_back(y[i]); for(i=1;i<=n;i++) maxn[x[i]]=max(maxn[x[i]],y[i]),minn[x[i]]=min(minn[x[i]],y[i]); for(i=1;i<=n;i++) s1[y[i]]=min(s1[y[i]],x[i]),s2[y[i]]=max(s2[y[i]],x[i]); for(i=1;i<=2*n;i++){ longge=s[i].size(); for(j=0;j<longge;j++) { last=s[i][j]; if(s1[last]==i) get(last,1); if(s2[last]==i) get(last,-1); } if(longge<2) continue; for(j=0;j<longge;j++){ last=s[i][j]; if(i!=s2[last]) ans--; } ans+=find(maxn[i])-find(minn[i]-1); //printf("%d\n",ans); } printf("%lld\n",ans+n); }