JYZdalao上課講了這道題，覺得很好可做

其實也是一道理解了就水爆了的題目

把題意抽象化，可以發現題目求的滿足

• i<j

• a[i]>=j

• a[j]>=i

的i，j對數。由于i，j順序問題，可以在不考慮i，j順序的情況下將ans>>1

如果題目只要求前兩個條件，那就是求逆序對的個數，樹狀數組即可

但是這里還要求a[j]>=i，因此我們先把a排序一遍，然后把所有小于i的全部彈出

剩下的就是樹狀數組水一水了

注意a[i]=min(a[i],n+1）（太大了要爆內存，也沒有離散化的必要）

CODE

#include<cstdio> #include<algorithm> using namespace std; const int N=2e5+5; struct data {int x,num; }a[N]; int s[N],n,now; long long ans,tree[N]; inline char tc(void) {static char fl[100000],*A=fl,*B=fl;return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++; } inline void read(int &x) {x=0; char ch=tc();while (ch<'0'||ch>'9') ch=tc();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc(); } inline int min(int a,int b) {return a<b?a:b; } inline bool comp(data a,data b) {return a.x<b.x; } inline int lowbit(int x) {return x&(-x); } inline void add(int x,int y) {while (x<=n+1){tree[x]+=y;x+=lowbit(x);} } inline long long get(int x) {long long res=0;while (x){res+=tree[x];x-=lowbit(x);}return res; } int main() {register int i;//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);read(n);for (i=1;i<=n;++i){read(s[i]); s[i]=min(s[i],n+1);a[i].x=s[i]; a[i].num=i; add(i,1);}sort(a+1,a+n+1,comp);for (now=1,i=1;i<=n;++i){while (now<=n&&a[now].x<i) add(a[now++].num,-1);ans+=get(s[i]);if (i<=s[i]) --ans;}printf("%lld",ans>>1);return 0; }

轉載于:https://www.cnblogs.com/cjjsb/p/8734578.html

總結

以上是生活随笔為你收集整理的CF 961E Tufurama的全部內容，希望文章能夠幫你解決所遇到的問題。

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