首页 > 代码库 > CodeForces 61E Enemy is weak 求i<j<k && a[i]>a[j]>a[k] 的对数 树状数组
CodeForces 61E Enemy is weak 求i<j<k && a[i]>a[j]>a[k] 的对数 树状数组
题目链接:点击打开链接
题意是求 i<j<k && a[i]>a[j]>a[k] 的对数
如果只有2元组那就是求逆序数的做法
三元组的话就用一个树状数组x表示 数字i前面有多少个比自己大的个数
然后每次给这个y数组求和,再把x中>a[i]的个数存入y中即可
#include <algorithm> #include <cctype> #include <cassert> #include <cstdio> #include <cstring> #include <climits> #include <vector> #include<iostream> using namespace std; #define ll long long inline void rd(int &ret) { char c; do { c = getchar(); } while(c < '0' || c > '9'); ret = c - '0'; while((c=getchar()) >= '0' && c <= '9') ret = ret * 10 + ( c - '0' ); } #define N 1000005 #define eps 1e-8 #define inf 1000000 ll n; struct node{ ll c[N]; inline ll lowbit(ll x){return x&-x;} void init(){memset(c, 0, sizeof c);} ll sum(ll x){ ll ans = 0; while(x<=n+10) ans += c[x], x+=lowbit(x); return ans; } void change(ll x, ll y){ while(x) c[x] +=y, x-=lowbit(x); } }x, y; int haifei[1000000], panting[1000000]; int main() { ll i, j; while(cin>>n) { ll ans = 0; for(i = 0; i < n; i++)rd(haifei[i]), panting[i] = haifei[i]; x.init(); y.init(); sort(haifei, haifei+n); for(i = 0; i < n; i++) { ll b = (lower_bound(haifei, haifei+n, panting[i]) - haifei) +1; ll siz = y.sum(b); ans += siz; y.change(b, x.sum(b)); x.change(b, 1); } cout<<ans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。