Skip to content

Instantly share code, notes, and snippets.

@htfy96 htfy96/cdq.cpp
Last active Dec 19, 2018

Embed
What would you like to do?
Solution to CF Educational Round 56 Problem E, with CDQ divide-and-conquer (CDQ分治)
#include <bits/stdc++.h>
/*
https://codeforces.com/contest/1093/problem/E
Convert all modification and query into single-point events (t, x, y). Initially sort by t,
for each interval, recursively handle independent two parts. Then calc the interference
between part one and two: only mod in part 1 can affect result in part 2. Therefore, we can
sort part1 and 2 respectively by x, then process all mod event in part 1 and all query events in
part 2 in a sort-merge-like way. The Y-dimension is maintained with a fenwick tree.
In the end all elements will be sorted by x.
*/
vector<int> b;
struct Event {
enum Type {
ADDANS,
SUBANS,
ADD,
REMOVE
} type;
int t, x, y;
int ansid;
};
vector<Event> e;
vector<int> ans;
int n;
int m;
struct Fenwick {
vector<int> a;
Fenwick(int cap): a(cap+2) {}
static int lowbit(int x) {
return x & (-x);
}
int prefix(int p) {
++p;
int ans = 0;
while (p > 0)
{
ans += a[p];
p -= lowbit(p);
}
return ans;
}
void add(int p, int x) {
++p;
while (p < a.size()){
a[p] += x;
p += lowbit(p);
}
}
} f(1);
void cdq(int l, int r) {
if (l == r) return;
int mid = (l + r) / 2;
cdq(l, mid);
cdq(mid + 1, r);
static vector<Event> buf;
buf.clear();
buf.reserve(r-l+1);
int t1 = l, t2 = mid + 1;
while (t1 <= mid || t2 <= r)
if (t1 <= mid && (t2 > r || e[t1].x <= e[t2].x))
{
buf.push_back(e[t1]);
switch (e[t1].type) {
case Event::Type::ADD:
f.add(e[t1].y, 1);
break;
case Event::Type::REMOVE:
f.add(e[t1].y, -1);
break;
}
++t1;
} else {
buf.push_back(e[t2]);
switch (e[t2].type) {
case Event::Type::ADDANS:
ans[e[t2].ansid] += f.prefix(e[t2].y);
break;
case Event::Type::SUBANS:
ans[e[t2].ansid] -= f.prefix(e[t2].y);
break;
}
++t2;
}
for (int i=l; i<=mid; ++i)
switch (e[i].type) {
case Event::Type::ADD:
f.add(e[i].y, -1);
break;
case Event::Type::REMOVE:
f.add(e[i].y, 1);
break;
}
copy(buf.begin(), buf.end(), e.begin() + l);
}
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);ios_base::sync_with_stdio(0);
cin >> n >> m;
f = Fenwick(n+1);
vector<int> pos(n);
int t = 0;
for(int i=0;i<n;++i) {
int w;
cin >> w;
pos[w-1] = i;
}
for(int i=0;i<n;++i) {
int w;
cin >> w;
b.push_back(pos[w-1]);
e.push_back(Event{Event::Type::ADD, t++, i, pos[w-1]});
}
for(int i=0;i<m;++i) {
int q;
cin >> q;
if (q == 1)
{
int vl, vr, l, r;
cin >> vl >> vr >> l >> r;
--vl; --vr; --l; --r;
ans.push_back(0);
e.push_back(Event{Event::Type::ADDANS, t++, r, vr, (int)ans.size() - 1});
e.push_back(Event{Event::Type::ADDANS, t++, l-1, vl-1, (int)ans.size() - 1});
e.push_back(Event{Event::Type::SUBANS, t++, r, vl-1, (int)ans.size() - 1});
e.push_back(Event{Event::Type::SUBANS, t++, l-1, vr, (int)ans.size() - 1});
} else {
int p1, p2;
cin >> p1 >> p2;
--p1; --p2;
e.push_back(Event{Event::Type::REMOVE, t++, p1, b[p1]});
e.push_back(Event{Event::Type::REMOVE, t++, p2, b[p2]});
swap(b[p1], b[p2]);
e.push_back(Event{Event::Type::ADD, t++, p1, b[p1]});
e.push_back(Event{Event::Type::ADD, t++, p2, b[p2]});
}
}
cdq(0, t-1);
for (int v: ans)
cout << v << '\n';
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.