ZOJ - 2112【Dynamic Rankings】 带修改主席树 + 树状数组

https://cn.vjudge.net/contest/304073#problem/E

题意

• Q x y z —— 询问 [x, y] 区间里的第 z 小的数

• C x y —— 把第 x 个数变成 y

mmp突然想起来可以分块...

代码

``````#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

const int maxn = 5e4+5;

int n, m, cnt;
int root[maxn];
int a[maxn];
vector<int> v;
int new_n;
int S[maxn];    // 树状数组维护的新树
int use[maxn];  // use记录要操作的线段树下标

struct node {
int l, r, sum;
}T[maxn*40];

struct Question {
int f;
int a, b, c;
}Q[maxn];

void init() {
v.clear();
memset(root, 0, sizeof(root));
for(int i = 0; i <= n*40; i++) {
T[i].l = T[i].r = T[i].sum = 0;
}
cnt = 0;
}

int getid(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

int lowbit(int x) {
return x & (-x);
}

void build(int l, int r, int &rt) {
rt = ++cnt;
if(l == r) {
return ;
}
int mid = (l+r) / 2;
build(l, mid, T[rt].l);
build(mid+1, r, T[rt].r);
}

void update(int l, int r, int &x, int y, int pos, int f) {
T[++cnt] = T[y];
T[cnt].sum += f;    // 1 or -1
x = cnt;
if(l == r)
return ;
int mid = (l+r) / 2;
if(mid >= pos) {
update(l, mid, T[x].l, T[y].l, pos, f);
}
else {
update(mid+1, r, T[x].r, T[y].r, pos, f);
}
}

void Add(int x, int c, int f) {
while(x <= n) {
update(1, new_n, S[x], S[x], c, f);
x += lowbit(x);
}
}

int Sum(int x) {
int ans = 0;
while(x > 0) {
ans += T[T[use[x]].l].sum;
x -= lowbit(x);
}
return ans;
}

int query(int l, int r, int a, int b, int x, int y, int k) {
if(l == r) {
return l;
}
int mid = (l+r) / 2;
int sum = Sum(b) - Sum(a) + T[T[y].l].sum - T[T[x].l].sum;
if(sum >= k) {
for(int i = a; i > 0; i -= lowbit(i)) {
use[i] = T[use[i]].l;
}
for(int i = b; i > 0; i -= lowbit(i)) {
use[i] = T[use[i]].l;
}
return query(l, mid, a, b, T[x].l, T[y].l, k);
}
else {
for(int i = a; i > 0; i -= lowbit(i)) {
use[i] = T[use[i]].r;
}
for(int i = b; i > 0; i -= lowbit(i)) {
use[i] = T[use[i]].r;
}
return query(mid+1, r, a, b, T[x].r, T[y].r, k-sum);
}
}

int main() {
// fopen("in.txt", "r", stdin);
// fopen("out.txt", "w", stdout);
int t;
scanf("%d", &t);
while(t--) {
init();
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
v.push_back(a[i]);
}
for(int i = 1; i <= m; i++) {
char f[10];
scanf("%s", f);
if(f[0] == 'Q') {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
Q[i].f = 0;
Q[i].a = l;
Q[i].b = r;
Q[i].c = k;
}
else {
int x, c;
scanf("%d%d", &x, &c);
Q[i].f = 1;
Q[i].a = x;
Q[i].b = c;
v.push_back(c);
}
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
new_n = (int)v.size();
for(int i = 1; i <= n; i++) {
update(1, new_n, root[i], root[i-1], getid(a[i]), 1);
}
for(int i = 1; i <= n; i++) {
S[i] = root[0];
}
for(int i = 1; i <= m; i++) {
if(Q[i].f == 0) {
for(int j = Q[i].a-1; j > 0; j-= lowbit(j)) {
use[j] = S[j];
}
for(int j = Q[i].b; j > 0; j -= lowbit(j)) {
use[j] = S[j];
}
int ans = query(1, new_n, Q[i].a-1, Q[i].b, root[Q[i].a-1], root[Q[i].b], Q[i].c) - 1;
printf("%d\n", v[ans]);
}
else {
a[Q[i].a] = Q[i].b;
}
}
}
return 0;
}``````

ZOJ - 2112【Dynamic Rankings】 带修改主席树 + 树状数组

(0)
(0)