1370 字
7 分钟
BZOJ 1901 [Zju2112] Dynamic Rankings
Description
给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1 ],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改 变后的a继续回答上面的问题。
Input
第一行一个数字N,代表测试组数 对于每组数据第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。 分别表示序列的长度和指令的个数。 第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。 接下来的m行描述每条指令 每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1) 表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。 C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t
Output
对于每一次询问,你都需要输出他的答案,每一个输出占单独的一行。
Sample Input
1
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
题解
简单的来说就是待修改的区间k小值
我们用让线段树外面套一层树状数组就可以修改了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1000000000;
#define lowbit(_) ((_) & (-_))
struct Seg_Node
{
Seg_Node *ch[2];
int sum, l, r;
Seg_Node(int L, int R)
{
sum = 0, l = L, r = R;
ch[1] = ch[0] = NULL;
}
#define sum(_) ((_) ? (_)->sum : 0)
void Pushup()
{
sum = sum(ch[0]) + sum(ch[1]);
}
} * root[50005];
int a[50005];
int n;
void Insert(Seg_Node *rt, int num)
{
if (rt->l == rt->r)
{
rt->sum++;
return;
}
int m = rt->l + rt->r >> 1;
if (num <= m)
{
if (!rt->ch[0])
rt->ch[0] = new Seg_Node(rt->l, m);
Insert(rt->ch[0], num);
}
else
{
if (!rt->ch[1])
rt->ch[1] = new Seg_Node(m + 1, rt->r);
Insert(rt->ch[1], num);
}
rt->Pushup();
}
void Insert(int x, int num)
{
for (int i = x; i <= n; i += lowbit(i))
{
if (root[i] == NULL)
root[i] = new Seg_Node(0, N);
Insert(root[i], num);
}
}
void Delete(Seg_Node *&rt, int num)
{
if (rt->l == rt->r)
{
rt->sum--;
if (!rt->sum)
delete rt, rt = NULL;
return;
}
int m = rt->l + rt->r >> 1;
if (num <= m)
Delete(rt->ch[0], num);
else
Delete(rt->ch[1], num);
rt->Pushup();
if (!rt->sum)
delete rt, rt = NULL;
}
void Delete(int x, int num)
{
for (int i = x; i <= n; i += lowbit(i))
{
Delete(root[i], num);
}
}
vector<Seg_Node *> Get(int x)
{
vector<Seg_Node *> ans;
for (int i = x; i > 0; i -= lowbit(i))
{
ans.push_back(root[i]);
}
return ans;
}
vector<Seg_Node *> Get_ch(vector<Seg_Node *> x, int op)
{
for (int i=0;i<x.size();i++)
if (x[i])
x[i] = x[i]->ch[op];
return x;
}
int Query(vector<Seg_Node *> list1, vector<Seg_Node *> list2, int l, int r, int k)
{
if (l == r)
return l;
int ans = 0;
for (int i=0;i<list2.size();i++)
if (list2[i])
ans += sum(list2[i]->ch[0]);
for (int i=0;i<list1.size();i++)
if (list1[i])
ans -= sum(list1[i]->ch[0]);
int m = l + r >> 1;
if (ans >= k)
return Query(Get_ch(list1, 0), Get_ch(list2, 0), l, m, k);
else
return Query(Get_ch(list1, 1), Get_ch(list2, 1), m + 1, r, k - ans);
}
void DFS(Seg_Node *&rt)
{
if (rt)
{
DFS(rt->ch[0]);
DFS(rt->ch[1]);
delete rt;
rt=NULL;
}
}
void remove()
{
for (int i = 1; i <= n; i++)
{
DFS(root[i]);
}
}
int main(int argc, char const *argv[])
{
//freopen("dynrank.in","r",stdin);
//freopen("dynrank.out","w",stdout);
//int T;
//scanf("%d", &T);
//while (T--)
//{
int m;
scanf("%d%d", &n, &m);
//memset(a,0,sizeof(a));
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
Insert(i, a[i]);
}
//sort(a + 1, a + n + 1);
char op[3];
int p, b, c;
for (int i = 1; i <= m; i++)
{
scanf("%s", op);
if (op[0] == 'Q')
{
scanf("%d%d%d", &p, &b, &c);
printf("%d\n", Query(Get(p - 1), Get(b), 0, N, c));
}
else
{
scanf("%d%d", &p, &b);
Delete(p, a[p]);
Insert(p, b);
a[p] = b;
}
}
remove();
// }
return 0;
}
树套树
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[50005], n;
class Treap
{
class Node
{
public:
int size, v, key;
Node *ch[2];
Node(int x)
{
key = rand();
v = x;
size = 1;
ch[0] = ch[1] = NULL;
}
#define size(_) ((_) ? (_)->size : 0)
void Pushup()
{
size = size(ch[0]) + size(ch[1]) + 1;
}
} * root;
Node *Merge(Node *A, Node *B)
{
if (!A)
return B;
if (!B)
return A;
if (A->key > B->key)
{
A->ch[1] = Merge(A->ch[1], B);
A->Pushup();
return A;
}
else
{
B->ch[0] = Merge(A, B->ch[0]);
B->Pushup();
return B;
}
}
typedef pair<Node *, Node *> DNode;
DNode Split(Node *rt, int k)
{
if (!rt)
return DNode(NULL, NULL);
DNode o;
if (size(rt->ch[0]) >= k)
{
o = Split(rt->ch[0], k);
rt->ch[0] = o.second;
rt->Pushup();
o.second = rt;
}
else
{
o = Split(rt->ch[1], k - size(rt->ch[0]) - 1);
rt->ch[1] = o.first;
rt->Pushup();
o.first = rt;
}
return o;
}
public:
Treap()
{
root = NULL;
}
int kth(int k)
{
DNode x = Split(root, k - 1);
DNode y = Split(x.second, 1);
Node *ans = y.first;
root = Merge(x.first, Merge(y.first, y.second));
return ans->v;
}
int rank(int x)
{
return rank(root, x);
}
int rank(Node *rt, int x)
{
if (!rt)
return 0;
return x <= rt->v ? rank(rt->ch[0], x) : rank(rt->ch[1], x) + size(rt->ch[0]) + 1;
}
void Insert(int x)
{
int k = rank(root, x);
DNode y = Split(root, k);
Node *n = new Node(x);
root = Merge(Merge(y.first, n), y.second);
}
void remove(int x)
{
int k = rank(root, x);
DNode a = Split(root, k);
DNode b = Split(a.second, 1);
root = Merge(a.first, b.second);
}
} root[50005 << 2];
#define lch l, m, rt << 1
#define rch m + 1, r, rt << 1 | 1
void build(int l, int r, int rt)
{
for (int i = l; i <= r; i++)
root[rt].Insert(a[i]);
}
void buildtree(int l, int r, int rt)
{
build(l, r, rt);
if (l == r)
return;
int m = l + r >> 1;
buildtree(lch);
buildtree(rch);
}
void updata(int k, int x, int y, int l, int r, int rt)
{
root[rt].remove(y);
root[rt].Insert(x);
if (l == r)
return;
int m = l + r >> 1;
if (k <= m)
updata(k, x, y, lch);
else
updata(k, x, y, rch);
}
int rank(int L, int R, int x, int l, int r, int rt)
{
if (L <= l && R >= r)
return root[rt].rank(x);
int m = l + r >> 1;
if (R <= m)
return rank(L, R, x, lch);
if (L > m)
return rank(L, R, x, rch);
return rank(L, R, x, lch) + rank(L, R, x, rch);
}
int kth(int L, int R, int k)
{
int l = -1e10, r = 1e10;
while (l <= r)
{
int m = l + r >> 1;
int num = rank(L, R, m, 1, n, 1) + 1;
if (num <= k)
l = m + 1;
else
r = m - 1;
}
return r;
}
int main()
{
//freopen("dynrank.in", "r", stdin);
//freopen("dynrank.out", "w", stdout);
//int T;
//scanf("%d", &T);
//while (T--)
//{
// memset(root,0,sizeof(root));
int m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
buildtree(1, n, 1);
char s[5];
int i, j, k, t;
while (m--)
{
scanf("%s", s);
if (s[0] == 'Q')
{
scanf("%d%d%d", &i, &j, &k);
printf("%d\n", kth(i, j, k));
}
else
{
scanf("%d%d", &i, &t);
updata(i, t, a[i], 1, n, 1);
a[i] = t;
}
}
//}
}
BZOJ 1901 [Zju2112] Dynamic Rankings
https://www.nekomio.com/posts/55/