| 记录编号 |
324073 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
动态排名系统 |
最终得分 |
100 |
| 用户昵称 |
 sxysxy |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
4.430 s |
| 提交时间 |
2016-10-17 19:13:16 |
内存使用 |
4.51 MiB |
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <list>
#include <queue>
#include <list>
using namespace std;
int fast_read()
{
int r;
char c;
while(c = getchar())
{
if(c >= '0' && c <= '9')
{
r = c^0x30;
break;
}
}
while(isdigit(c = getchar()))
r = (r<<3)+(r<<1)+(c^0x30);
return r;
}
//AVL平衡树
typedef struct _AVL
{
struct _AVL *left, *right;
int data;
int height;
int size;
}AVLNode, *pNode, *AVLTree;
#define HEIGHT(x) ((x)?(x)->height:-1)
#define SIZE(x) ((x)?(x)->size:0)
void momomo(pNode k)
{
if(k)
{
k -> height = max(HEIGHT(k -> left), HEIGHT(k -> right)) + 1;
k -> size = SIZE(k -> left) + SIZE(k -> right) + 1;
}
}
pNode singleRotateLL(pNode k)
{
pNode k1 = k -> left;
k -> left = k1 -> right;
k1 -> right = k;
momomo(k);
momomo(k1);
return k1;
}
pNode singleRotateRR(pNode k)
{
pNode k1 = k -> right;
k -> right = k1 -> left;
k1 -> left = k;
momomo(k);
momomo(k1);
return k1;
}
pNode doubleRotateLR(pNode k)
{
k -> left = singleRotateRR(k -> left);
return singleRotateLL(k);
}
pNode doubleRotateRL(pNode k)
{
k -> right = singleRotateLL(k -> right);
return singleRotateRR(k);
}
AVLTree insert(AVLTree t, int x)
{
if(!t)
{
t = new AVLNode;
t -> data = x;
t -> size = 1;
t -> left = t -> right = 0;
}else
{
if(x < t -> data)
{
t -> left = insert(t -> left, x);
if(HEIGHT(t -> left) - HEIGHT(t -> right) == 2)
{
if(x < t -> left -> data)
t = singleRotateLL(t);
else
t = doubleRotateLR(t);
}
}else
{
t -> right = insert(t -> right, x);
if(HEIGHT(t -> right) - HEIGHT(t -> left) == 2)
{
if(x >= t -> right -> data)
t = singleRotateRR(t);
else
t = doubleRotateRL(t);
}
}
}
momomo(t);
return t;
}
pNode delBalance(pNode k)
{
if(HEIGHT(k -> right) - HEIGHT(k -> left) == 2)
{
if(k -> right)
{
if(HEIGHT(k -> right -> right) >= HEIGHT(k -> right -> left))
k = singleRotateRR(k);
else
k = doubleRotateRL(k);
}
}
if(HEIGHT(k -> left) - HEIGHT(k -> right) == 2)
{
if(k -> left)
{
if(HEIGHT(k -> left -> left) >= HEIGHT(k -> left -> right))
k = singleRotateLL(k);
else
k = doubleRotateLR(k);
}
}
momomo(k);
return k;
}
AVLTree delNode(AVLTree t, int x)
{
if(!t)
return NULL;
if(x == t -> data)
{
if(!t -> right)
{
pNode tmp = t;
t = t -> left;
free(tmp);
}else
{
pNode tmp = t -> right;
while(tmp -> left)
tmp = tmp -> left;
t -> data = tmp -> data;
t -> right = delNode(t -> right, t -> data);
}
momomo(t);
return t;
}
if(x < t -> data)
{
t -> left = delNode(t -> left, x);
}else
{
t -> right = delNode(t -> right, x);
}
if(t -> left)
t -> left = delBalance(t -> left);
if(t -> right)
t -> right = delBalance(t -> right);
if(t)
t = delBalance(t);
return t;
}
//<= x 的个数
int Smaller(pNode t, int x)
{
if(!t)return 0;
if(x < t -> data)
return Smaller(t -> left, x);
else
return 1 + SIZE(t -> left) + Smaller(t -> right, x);
}
#define MAXN 100002
int last = 0;
struct _SegNode
{
int ls, rs; //左右孩子
AVLTree rt; //这个节点的平衡树
int l, r;
}ns[MAXN<<1];
int data[MAXN];
int build(int l, int r)
{
int cur = ++last;
memset(ns+cur, 0, sizeof(_SegNode));
ns[cur].l = l;
ns[cur].r = r;
ns[cur].rt = NULL;
for(int i = l; i <= r; i++) //将区间l,r内的数全部插入平衡树
ns[cur].rt = insert(ns[cur].rt, data[i]);
if(l == r)
return cur;
int mid = (l+r)>>1;
if(l <= mid)
{
ns[cur].ls = build(l, mid);
ns[cur].rs = build(mid+1, r);
}
return cur;
}
//查询区间l, r内 <= n的数的个数
//第一个参数c是线段树节点的下标
int queryTree(int c, int l, int r, int n)
{
if(ns[c].l == l && ns[c].r == r)
return Smaller(ns[c].rt, n); // <= n的数的个数
int ls= ns[c].ls;
int rs = ns[c].rs;
if(r <= ns[ls].r) //l,r完全在左边
return queryTree(ls, l, r, n);
else if(l >= ns[rs].l) //右边
return queryTree(rs, l, r, n);
else //跨越中点，两段之和
return queryTree(ls, l, ns[ls].r, n) + queryTree(rs, ns[rs].l, r, n);
}
//修改第pos个数为v
void update(int c, int pos, int v)
{
ns[c].rt = delNode(ns[c].rt, data[pos]); //删掉原来的数
ns[c].rt = insert(ns[c].rt, v); //插入新的数
int ls = ns[c].ls;
int rs = ns[c].rs;
if(ls && pos >= ns[ls].l && pos <= ns[ls].r) //更新左右子树
update(ls, pos, v);
else if(rs && pos >= ns[rs].l && pos <= ns[rs].r)
update(rs, pos, v);
}
void change(int pos, int v)
{
update(1, pos, v);
data[pos] = v; //记录最后一次data[pos]的值
}
int solve(int l, int r, int k)
{
int x = 0;
int y = 0x7fffffff; //二分答案
int ans = 0;
while(x <= y)
{
int mid = (x+y)>>1;
int f = queryTree(1, l, r, mid); // l,r内 <= mid的数的个数
if(f >= k)
{
y = mid-1;
ans = mid;
}
else
x = mid+1;
}
return ans;
}
int main()
{
freopen("dynrank.in", "r", stdin);
freopen("dynrank.out", "w", stdout);
int d = fast_read();
while(d--)
{
int n, m;
n = fast_read();
m = fast_read();
for(int i = 1; i <= n; i++)
data[i] = fast_read();
last = 0;
build(1, n);
while(m--)
{
char c;
while(c = getchar())
if(c == 'Q' || c == 'C')break;
if(c == 'Q')
{
int a, b, c;
a = fast_read();
b = fast_read();
c = fast_read();
printf("%d\n", solve(a, b, c));
}else if(c == 'C')
{
int a, b;
a = fast_read();
b = fast_read();
change(a, b);
}
}
}
return 0;
}