南通公司快速建站,史志网站建设必要性,品牌推广策略ppt,东莞微网站制作JYZdalao上课讲了这道题#xff0c;觉得很好可做 其实也是一道理解了就水爆了的题目 把题意抽象化#xff0c;可以发现题目求的满足 ija[i]ja[j]i的i#xff0c;j对数。由于i#xff0c;j顺序问题#xff0c;可以在不考虑i#xff0c;j顺序的情况下将ans… JYZdalao上课讲了这道题觉得很好可做 其实也是一道理解了就水爆了的题目 把题意抽象化可以发现题目求的满足 ija[i]ja[j]i的ij对数。由于ij顺序问题可以在不考虑ij顺序的情况下将ans1 如果题目只要求前两个条件那就是求逆序对的个数树状数组即可 但是这里还要求a[j]i因此我们先把a排序一遍然后把所有小于i的全部弹出 剩下的就是树状数组水一水了 注意a[i]min(a[i],n1太大了要爆内存也没有离散化的必要 CODE #includecstdio
#includealgorithm
using namespace std;
const int N2e55;
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],*Afl,*Bfl;return AB(B(Afl)fread(fl,1,100000,stdin),AB)?EOF:*A;
}
inline void read(int x)
{x0; char chtc();while (ch0||ch9) chtc();while (ch0ch9) xx*10ch-0,chtc();
}
inline int min(int a,int b)
{return ab?a:b;
}
inline bool comp(data a,data b)
{return a.xb.x;
}
inline int lowbit(int x)
{return x(-x);
}
inline void add(int x,int y)
{while (xn1){tree[x]y;xlowbit(x);}
}
inline long long get(int x)
{long long res0;while (x){restree[x];x-lowbit(x);}return res;
}
int main()
{register int i;//freopen(CODE.in,r,stdin); freopen(CODE.out,w,stdout);read(n);for (i1;in;i){read(s[i]); s[i]min(s[i],n1);a[i].xs[i]; a[i].numi; add(i,1);}sort(a1,an1,comp);for (now1,i1;in;i){while (nowna[now].xi) add(a[now].num,-1);ansget(s[i]);if (is[i]) --ans;}printf(%lld,ans1);return 0;
} 转载于:https://www.cnblogs.com/cjjsb/p/8734578.html
