ZOJ 2011-Dynamic Rankingsツリーセット?
この問題はさっきlrjの問題に虐げられてから書いたもので、この問題の問題はN個の数のシーケンスを教えて、毎回1つの位置の値を修正して、動的に区間のk番目の要素を検索します
方法は1つのセグメントツリーを維持することで、このように私たちは区間の情報を得ることができますが、この時私たちは区間の秩序あるシーケンスを維持することはできません.だから、私たちは2分の答えを求めて、lからrの区間内でこの数より小さいものがどれだけあるかを調べて、kと比較して、それから最後に答えを得て、1つのセグメントツリーと1つのバランスツリーを書きます.普段データ構造を書くことが多い場合、コード量は普通で、私のコードはずっと長くて、200行ぐらい書きました.
方法は1つのセグメントツリーを維持することで、このように私たちは区間の情報を得ることができますが、この時私たちは区間の秩序あるシーケンスを維持することはできません.だから、私たちは2分の答えを求めて、lからrの区間内でこの数より小さいものがどれだけあるかを調べて、kと比較して、それから最後に答えを得て、1つのセグメントツリーと1つのバランスツリーを書きます.普段データ構造を書くことが多い場合、コード量は普通で、私のコードはずっと長くて、200行ぐらい書きました.
/*
* Author: Fish@UESTC_Obsidian
* Created Time: 2011/09/30 18:40:59
* Project: ZOJ2112-Dynamic_Rankings
* Type: ds
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX = 50005;
const int oo = 0x3f3f3f3f;
struct Node
{
int key, size;
Node* c[2];
} memo[MAX * 20], *cur, *nil;
int a[MAX], n, q;
struct Seg
{
int l, r;
Node* root;
} seg[MAX << 2];
inline Node* New(int v)
{
cur->key = v;
cur->size = 1;
cur->c[0] = cur->c[1] = nil;
return cur++;
}
inline void rotate(Node*& t, int f)
{
Node* k = t->c[f ^ 1];
t->c[f ^ 1] = k->c[f];
k->c[f] = t;
k->size = t->size;
t->size = t->c[0]->size + t->c[1]->size + 1;
t = k;
}
inline void keep(Node*& t, int f)
{
if (t == nil) return;
else if (t->c[f]->c[f]->size > t->c[f ^ 1]->size) rotate(t, f ^ 1);
else if (t->c[f]->c[f ^ 1]->size > t->c[f ^ 1]->size) rotate(t->c[f], f), rotate(t, f ^ 1);
else return;
for (int i = 0; i < 2; i++) keep(t->c[i], i);
for (int i = 0; i < 2; i++) keep(t, i);
}
inline void insert(Node*& t, int v)
{
if (t == nil)
{
t = New(v);
}
else
{
t->size++;
insert(t->c[v >= t->key], v);
keep(t, v >= t->key);
}
}
inline Node* del(Node*& t, int v)
{
Node* p;
if (t == nil) return nil;
t->size--;
if (v == t->key || t->c[v > t->key] == nil)
{
if (t->c[0] != nil && t->c[1] != nil) p = del(t->c[0], v + 1), t->key = p->key;
else p = t, t = t->c[t->c[0] == nil];
return p;
}
else return del(t->c[v > t->key], v);
}
inline int getRank(Node* t, int v)
{
int ret = 0;
while (t != nil)
if (t->key < v) ret += t->c[0]->size + 1, t = t->c[1];
else t = t->c[0];
return ret;
}
inline void init()
{
nil = cur = memo;
nil = New(0);
nil->size = 0;
}
inline void init(int k, int l, int r)
{
seg[k].l = l;
seg[k].r = r;
seg[k].root = nil;
for (int i = l; i <= r; i++)
{
insert(seg[k].root, a[i]);
}
if (l == r) return;
int mid = l + r >> 1;
init(k << 1, l, mid);
init(k << 1 | 1, mid + 1, r);
}
inline void set(int k, int idx, int v)
{
del(seg[k].root, a[idx]);
insert(seg[k].root, v);
if (seg[k].l == seg[k].r) return;
int mid = seg[k].l + seg[k].r >> 1;
if (idx <= mid) set(k << 1, idx, v);
else set(k << 1 | 1, idx, v);
}
inline int read(int k, int l, int r, int v)
{
if (l > r || seg[k].l > r || seg[k].r < l) return 0;
if (seg[k].l >= l && seg[k].r <= r)
{
return getRank(seg[k].root, v);
}
return read(k << 1, l, r, v) + read(k << 1 | 1, l, r, v);
}
inline int doit(int lb, int rb, int k)
{
int l = -1000000005, r = 1000000005, mid;
int ret;
while (l < r)
{
mid = l + r + 1 >> 1;
ret = read(1, lb, rb, mid);
if (ret < k) l = mid;
else r = mid - 1;
}
return l;
}
inline void doit()
{
char op[5];
int l, r, k;
init();
init(1, 1, n);
while (q--)
{
scanf("%s", op);
if (op[0] == 'Q')
{
scanf("%d%d%d", &l, &r, &k);
printf("%d
", doit(l, r, k));
}
else
{
scanf("%d%d", &l, &r);
set(1, l, r);
a[l] = r;
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
doit();
}
return 0;
}