ACM-ICPC 2018 青岛赛区网络预赛 G.Couleur (逆序对、主席树)
发布时间
阅读量：
阅读量
传送门：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5808
题意：
给定一个序列，在每一轮操作中会删除一个元素并将其分割为两个子序列；问题在于确定在每一轮操作之前，在当前所有分割后的子序列中逆序对的数量达到最大值时的具体情况；该问题要求在线查询并强制在线处理。
思路：
通过主席树算法每次可以在O(\log n)的时间内计算得到一个点在一个区间内的逆序对数量，在初始状态下（即未删除任何元素时），我们需要先统计整个数组的初始逆序对数量。
在每次删除操作中，在拆分后的各个小区间中直接计算其各自的逆序对数量；然后将大区间的逆序对数量基于这些小区间的计算结果来确定。
以左边为小区间为例： del 将要被删除的点，tot 原先该区间的逆序对数。
①利用主席树暴力算左区间内部有多少逆序对 lcnt 。
②求解左子数组中每一个数值与（del + 右子数组）之间逆序对的数量总和，并即为左子数组中所有元素相对于右子数组所形成的原始交叉逆序对数目与临时变量temp的总和
③计算 del 与右区间的逆序对数量 dcnt 。
剩下的左区间的内部逆序对数量等于 tot 减去 left_cnt 再减去 temporal 和 delta。
如果右边为小区间也类似计算就可以了。
答案值可以使用multiset用于维护；被删除的位置可以使用set用于存储；任意一个区间的逆序对数可以通过map记录
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<utility>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<ctime>
#include<functional>
#include<bitset>
#define P pair<int,int>
#define ll long long
#define ull unsigned long long
#define lson id*2,l,mid
#define rson id*2+1,mid+1,r
#define ls id*2
#define rs (id*2+1)
#define Mod(a,b) a<b?a:a%b+b
#define cl0(a) memset(a,0,sizeof(a))
#define cl1(a) memset(a,-1,sizeof(a))
using namespace std;
const ll M = 1e9 + 7;
const ll INF = 1e9;
const int N = 410;
const double _e = 10e-6;
const int maxn = 1e5 + 10;
const int matSize = 9;
const int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
const int _dx[8] = { -1,-1,-1,0,0,1,1,1 }, _dy[8] = { -1,0,1,-1,1,-1,0,1 };
int x, y;
int n, m;
int c[maxn];
map<int, ll> mp;
set<int> s; multiset<ll> ms;
struct chairtree { int l, r; ll cnt; }t[maxn << 5];
int root[maxn], a[maxn];
int lens, tot;
int build(int l, int r)
{
int id = ++tot;
t[id].cnt = 0;
if (l == r) return id;
int mid = (l + r) / 2;
t[id].l = build(l, mid); t[id].r = build(mid + 1, r);
return id;
}
int update(int id, int l, int r, int x)
{
int now = ++tot;
t[now].cnt = t[id].cnt + 1;
if (l == r)
return now;
int mid = (l + r) / 2;
if (x <= mid) {
t[now].r = t[id].r;
t[now].l = update(t[id].l, l, mid, x);
}
else {
t[now].l = t[id].l;
t[now].r = update(t[id].r, mid + 1, r, x);
}
return now;
}
ll query(int lid, int rid, int l, int r, int _l, int _r)
{
if (l == _l&&r == _r)
return t[rid].cnt - t[lid].cnt;
int mid = (l + r) / 2;
if (_r <= mid)
return query(t[lid].l, t[rid].l, l, mid, _l, _r);
else if (_l > mid)
return query(t[lid].r, t[rid].r, mid + 1, r, _l, _r);
else
return query(t[lid].l, t[rid].l, l, mid, _l, mid) + query(t[lid].r, t[rid].r, mid + 1, r, mid + 1, _r);
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
ll ans = 0; tot = 0; lens = n + 1;
mp.clear(); s.clear(); ms.clear();
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
root[0] = build(1, lens);
for (int i = 1; i <= n; i++) {
ans += query(root[0], root[i - 1], 1, lens, a[i] + 1, lens);
root[i] = update(root[i - 1], 1, lens, a[i]);
}
s.insert(0); s.insert(lens); ms.insert(ans); mp[0] = ans;
for (int i = 1; i < n; i++) {
printf("%lld ", ans);
if (ans == 0)continue;
int del = c[i] ^ ans;
auto it = s.upper_bound(del);
int l, r = *it; it--; l = *it;
ll lcnt, rcnt, temp = 0;
if (del - l <= r - del) {
lcnt = 0, rcnt = mp[l]; ms.erase(ms.lower_bound(rcnt));
for (int j = l + 1; j < del; j++) {
if (a[j] > 1) {
temp += query(root[j], root[del - 1], 1, lens, 1, a[j] - 1);
rcnt -= query(root[del - 1], root[r - 1], 1, lens, 1, a[j] - 1);
}
}
lcnt += temp; rcnt -= temp;
if (a[del] > 1)
rcnt -= query(root[del], root[r - 1], 1, lens, 1, a[del] - 1);
}
else {
lcnt = mp[l], rcnt = 0; ms.erase(ms.lower_bound(lcnt));
for (int j = del + 1; j < r; j++) {
temp += query(root[del], root[j - 1], 1, lens, a[j] + 1, lens);
lcnt -= query(root[l], root[del], 1, lens, a[j] + 1, lens);
}
lcnt -= temp; rcnt += temp;
lcnt -= query(root[l], root[del - 1], 1, lens, a[del] + 1, lens);
}
ms.insert(lcnt); ms.insert(rcnt);
mp[l] = lcnt; mp[del] = rcnt;
auto itt = ms.end(); itt--; ans = *itt;
s.insert(del);
}
printf("%lld\n", ans);
}
return 0;
}全部评论 (0)
还没有任何评论哟~