Little Artem and Time Machine CodeForces-669 E(CDQ分治)
2225 ワード
テーマリンク:http://codeforces.com/problemset/problem/669/E
n個の操作をあげます.全部で3種類です.
1、op=1、時間tに数を追加
2、op=2、時間tで1つの数を削除
3、op=3、クエリが時間tに現れる回数
3 Dバイアス問題は,CDQで解決できるか,2 Dツリー配列で直接やるか,動的議長ツリー(書くのが面倒)である.
n個の操作をあげます.全部で3種類です.
1、op=1、時間tに数を追加
2、op=2、時間tで1つの数を削除
3、op=3、クエリが時間tに現れる回数
3 Dバイアス問題は,CDQで解決できるか,2 Dツリー配列で直接やるか,動的議長ツリー(書くのが面倒)である.
#include
#define ll long long
using namespace std;
const int maxn = 1e5 + 30;
struct node{
int x, y, z, id, op;
int val;
}q[maxn * 5], tmp[maxn * 5];
int ans[maxn * 5], num[maxn * 5];
bool cmp(node x, node y){
if(x.x != y.x) return x.x < y.x;
else if(x.y != y.y) return x.y < y.y;
return x.z < y.z;
}
bool cmp1(node x, node y){
return x.id < y.id;
}
void CDQ(int l, int r){
if(r - l <= 1) {
return;
}
int mid = l + r >> 1;
CDQ(l, mid);
CDQ(mid, r);
int t1 = l, t2 = mid, cnt = 0;
while(t1 < mid && t2 < r){
if(q[t1].y <= q[t2].y){
if(q[t1].op == 1) num[q[t1].z]++;
else if(q[t1].op == 2) num[q[t1].z]--;
tmp[cnt++] = q[t1++];
}
else {
if(q[t2].op == 3) ans[q[t2].id] += num[q[t2].z];
tmp[cnt++] = q[t2++];
}
}
while(t1 < mid) tmp[cnt++] = q[t1++];
while(t2 < r){
if(q[t2].op == 3) ans[q[t2].id] += num[q[t2].z];
tmp[cnt++] = q[t2++];
}
for(int i = 0; i < cnt; i++) {
q[i + l] = tmp[i];
num[tmp[i].z] = 0;
}
}
int b[maxn];
int main()
{
int n, m, qq;
while(~scanf("%d", &n)){
for(int i = 0; i < n; i++) {
int x, y;
scanf("%d%d%d", &q[i].op, &x, &y);
q[i].val = 1;
q[i].id = i + 1;
q[i].x = i;
q[i].y = x;
q[i].z = y;
b[i] = y;
}
sort(b, b + n);
int len = unique(b, b + n) - b;
for(int i = 0; i < n; i++) {
q[i].z = lower_bound(b, b + len, q[i].z) - b + 1;
}
for(int i = 0; i <= n; i++) ans[i] = 0;
CDQ(0, n);
sort(q, q + n, cmp1);
for(int i = 0; i < n; i++) {
if(q[i].op == 3)
printf("%d
", ans[q[i].id]);
}
}
return 0;
}