BZOJ 3333: 排队计划 树状数组+线段树
题目大意:给出一个序列,求出这个序列的逆序对数量。定义一种操作,将一个数和他后面比他小的数字拿出来排序, 然后再放回去,之后输出逆序对数。
思路:思路题。手动模拟一下,会发现,逆序对变化的只是排序的那些点 。所以我们只要处理那些点就行了。先求一次逆序对,然后每次在拿出的数后面找到一个最小的数字,把它的权值改成INF,统计答案。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 500010 #define INF 0x3f3f3f3f using namespace std; #define LEFT (pos << 1) #define RIGHT (pos << 1|1) #define min(a,b) ((a) < (b) ? (a):(b)) int cnt,asks; pair<int,int *> xx[MAX]; int src[MAX],t; int inv[MAX]; int fenwick[MAX]; long long now; int tree[MAX << 2]; inline void Fix(int x) { for(; x <= t; x += x&-x) ++fenwick[x]; } inline int GetSum(int x) { int re = 0; for(; x; x -= x&-x) re += fenwick[x]; return re; } void BuildTree(int l,int r,int pos) { if(l == r) { tree[pos] = l; return ; } int mid = (l + r) >> 1; BuildTree(l,mid,LEFT); BuildTree(mid + 1,r,RIGHT); tree[pos] = src[tree[LEFT]] < src[tree[RIGHT]] ? tree[LEFT]:tree[RIGHT]; } int GetMin(int l,int r,int x,int y,int pos) { if(l == x && y == r) return tree[pos]; int mid = (l + r) >> 1; if(y <= mid) return GetMin(l,mid,x,y,LEFT); if(x > mid) return GetMin(mid + 1,r,x,y,RIGHT); int left = GetMin(l,mid,x,mid,LEFT); int right = GetMin(mid + 1,r,mid + 1,y,RIGHT); return src[left] < src[right] ? left:right; } void Modify(int l,int r,int x,int pos,int c) { if(l == r) return ; int mid = (l + r) >> 1; if(x <= mid) Modify(l,mid,x,LEFT,c); else Modify(mid + 1,r,x,RIGHT,c); tree[pos] = src[tree[LEFT]] < src[tree[RIGHT]] ? tree[LEFT]:tree[RIGHT]; } int main() { cin >> cnt >> asks; for(int i = 1; i <= cnt; ++i) { scanf("%d",&xx[i].first); xx[i].second = &src[i]; } sort(xx + 1,xx + cnt + 1); for(int i = 1; i <= cnt; ++i) { if(i == 1 || xx[i].first != xx[i - 1].first) ++t; *xx[i].second = t; } for(int i = cnt; i; --i) { inv[i] = GetSum(src[i] - 1); now += inv[i]; Fix(src[i]); } BuildTree(1,cnt,1); cout << now << endl; for(int temp,x,i = 1; i <= asks; ++i) { scanf("%d",&x); if(src[x] == INF) { printf("%lld\n",now); continue; } do { temp = GetMin(1,cnt,x,cnt,1); now -= inv[temp]; Modify(1,cnt,temp,1,src[temp] = INF); }while(temp != x); printf("%lld\n",now); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。