題目傳送門：https://atcoder.jp/contests/abc136/tasks/abc136_f

　　題目大意：在平面上有$n$個點我們，定義一個點集的權值為平面上包含這個點集的最小矩形所包含的點個數（矩形的邊與坐標軸平行），求所有非空點集的權值和，保證每個點的橫縱坐標互不相同。

　　先考慮轉化一下，求每個點被多少個點集$S$的矩形包含，假設我們當前考慮的是點$i$，那么可以分成兩種情況：$i \in S$或$i \notin S$。

　　　　1.?對于$i \in S$的情況，容易發現點$i$對所有包含$i$的點集有貢獻，這里的貢獻為$2^(n-1)$。

　　　　2.?對于$i \notin S$的情況，因為每個點的橫縱坐標互不相同，所以點$i$把整個坐標系劃分成了4個區域

　　　　那么若點集$S$的矩形包含點$i$，那么必存在$p,q \in S,p \in A,q \in D$或$p \in B,q \in D$。

　　　　設$A$區域中的點數量為$a$，$B$區域中的點數量為$b$，$C$區域中的點數量為$c$，$D$區域中的點數量為$d$，容斥可知這里的貢獻為$(2^a-1)2^b2^c(2^d-1)+2^a(2^b-1)(2^c-1)2^d-(2^a-1)(2^b-1)(2^c-1)(2^d-1)$。

　　計算每個區域的點數可以將點排序離散化后用樹狀數組維護，于是就可以在$O(n \log n)$的時間復雜度下解決問題。

　　代碼：

#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #define ll long long #define mod 998244353 #define maxn 200010 inline ll read() {ll x=0; char c=getchar(),f=1;for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';return x*f; } inline void write(ll x) {static char buf[20],len; len=0;if(x<0)x=-x,putchar('-');for(;x;x/=10)buf[len++]=x%10+'0';if(!len)putchar('0');else while(len)putchar(buf[--len]); } inline void writesp(ll x){write(x); putchar(' ');} inline void writeln(ll x){write(x); putchar('\n');} struct Data{int x,id; }num[maxn]; struct point{int x,y,rk; }a[maxn]; int n; bool cmp1(Data a,Data b){return a.x<b.x;} bool cmp2(point a,point b){return a.x<b.x;} inline ll power(ll a,ll b) {ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans; } int bit1[maxn],bit2[maxn]; void add1(int x,int k){for(;x<=n;x+=x&(-x))bit1[x]+=k;} int getsum1(int x){int sum=0; for(;x;x-=x&(-x))sum+=bit1[x]; return sum;} void add2(int x,int k){for(;x<=n;x+=x&(-x))bit2[x]+=k;} int getsum2(int x){int sum=0; for(;x;x-=x&(-x))sum+=bit2[x]; return sum;} int main() {n=read();for(int i=1;i<=n;i++){a[i].x=read(); a[i].y=read();num[i].x=a[i].y; num[i].id=i;}std::sort(num+1,num+n+1,cmp1);for(int i=1;i<=n;i++)a[num[i].id].rk=i;std::sort(a+1,a+n+1,cmp2);for(int i=1;i<=n;i++)bit1[i]=0,bit2[i]=i&(-i);ll ans=0;for(int i=1;i<=n;i++){add2(a[i].rk,-1);int A=getsum1(a[i].rk),B=getsum1(n)-getsum1(a[i].rk),C=getsum2(a[i].rk),D=getsum2(n)-getsum2(a[i].rk);ll totA=power(2,A),totB=power(2,B),totC=power(2,C),totD=power(2,D);ans=(ans+(totA-1)*totB%mod*totC%mod*(totD-1))%mod;ans=(ans+totA*(totB-1)%mod*(totC-1)%mod*totD)%mod;ans=(ans-(totA-1)*(totB-1)%mod*(totC-1)%mod*(totD-1)%mod+mod)%mod;ans=(ans+power(2,n-1))%mod;add1(a[i].rk,1);}writeln(ans);return 0; } abc136F

?

轉載于:https://www.cnblogs.com/quzhizhou/p/11300139.html

總結

以上是生活随笔為你收集整理的【atcoder】Enclosed Points [abc136F]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。