题目大意
写一种数据结构(可参考题目标题),维护有序数列,支持以下操作:
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)
解题报告
写的第一道树套树的题。。
这题解法比较多,有线段树套平衡树的,还可以离线主席树,~~据说还有套树状数组的?~~
我用的线段树套Treap(有段时间没写了)
首先使用线段树维护区间,然后每个线段树节点搞一个Treap维护区间内数字的权值,内存开销应该还是N的规模
1.对于第一种操作,排名等于区间内小于k的数数量+1,在线段树上找到询问的区间后到每个区间的Treap里查找k的rank累和就可以了。
2.对于第二中操作,在[0,1e18]内二分一下答案,然后检验就转化成了第一种操作,复杂度貌似爆到$Nlog^3N$。。
3.对于第三种操作,在线段树上找出包含修改的数字的区间然后再每个区间的Treap上暴力删除后再插入即可。
4.对于第四和第五种操作,结合使用第一和第二种操作就可以做出来啦!(懒癌)
思路也比较简单…就直接贴代码了
代码
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
inline int Random () {
return rand()*rand()*rand();
}
namespace treap {
const int MAXD = 4000000;
struct Node {
int val, ch[2], fa, prio;
int sz, cnt;
} d[MAXD];
int dtot; int * roothandle;
inline int newNode (int val) {
dtot ++;
d[dtot].val = val;
d[dtot].sz = 1;
d[dtot].cnt = 1;
d[dtot].prio = Random();
return dtot;
}
inline void updata (int u) {
d[u].sz = d[d[u].ch[0]].sz + d[u].cnt + d[d[u].ch[1]].sz;
}
inline void rotate (int x) {
int y = d[x].fa;
bool f = (d[y].ch[1] == x);
d[y].ch[f] = d[x].ch[!f];
d[x].ch[!f] = y;
d[d[y].ch[f]].fa = y;
d[x].fa = d[y].fa;
d[y].fa = x;
if(d[x].fa) d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
else (*roothandle) = x;
updata(y), updata(x);
}
int * src;
inline int build (int l, int r) {
if(l > r) return 0;
int mid = (l+r)>>1;
int u = newNode(src[mid]);
int lr = mid-1, rl = mid+1;
for(; lr >= l && src[lr] == src[mid]; lr--) d[u].sz ++, d[u].cnt ++;
for(; rl <= r && src[rl] == src[mid]; rl++) d[u].sz ++, d[u].cnt ++;
d[d[u].ch[0] = build(l, lr)].fa = u;
d[d[u].ch[1] = build(rl, r)].fa = u;
updata(u); return u;
}
inline int locate (int val, int mov = 0) {
int u = *roothandle;
while(u) {
d[u].sz += mov;
if(d[u].val == val) return u;
u = d[u].ch[d[u].val < val];
}
return u;
}
inline void erase (int u) {
d[u].cnt --;
if(d[u].cnt) return ;
while(d[u].ch[0] || d[u].ch[1])
if(d[u].ch[0] && (!d[u].ch[1] || d[d[u].ch[0]].prio > d[d[u].ch[1]].prio))
rotate(d[u].ch[0]);
else rotate(d[u].ch[1]);
if(d[u].fa) d[d[u].fa].ch[d[d[u].fa].ch[1] == u] = 0;
}
inline void insert (int val) {
int u = *roothandle, l = 0;
while(u) {
l = u; d[u].sz ++;
if(d[u].val == val) {d[u].cnt ++; return;}
u = d[u].ch[d[u].val < val];
}
u = newNode(val);
d[u].fa = l;
d[l].ch[d[l].val < val] = u;
while(d[u].fa && d[d[u].fa].prio <= d[u].prio) rotate(u);
}
inline int getRankByValue (int val) {
int u = *roothandle, rk = 0;
while(u) {
if(d[u].val < val) rk += d[u].cnt + d[d[u].ch[0]].sz, u = d[u].ch[1];
else if(d[u].val == val) return rk+d[d[u].ch[0]].sz;
else u = d[u].ch[0];
}
return rk;
}
}
const int MAXN = 51000;
namespace ibt {
const int MAXD = 400000;
struct Node {int l, r, uid;} d[MAXD];
int * src;
int temp[MAXD];
void build (int l, int r, int u = 1) {
d[u].l = l, d[u].r = r;
int mid = (l+r)>>1;
for(int i = l; i<=r; i++)
temp[i] = src[i];
std :: sort(temp+l, temp+r+1);
d[u].uid = treap :: build(l, r);
if(l == r) return ;
build(l, mid, u<<1), build(mid+1, r, (u<<1)+1);
}
int argl, argr, argk, argv;
inline void fillArgs (int a, int b = 0, int c = 0) {
argl = a, argr = b, argk = c;
}
int getRankByValue (int u = 1) {
if(d[u].r < argl || d[u].l > argr ) return 0;
if(d[u].l >= argl && d[u].r <= argr) {
treap :: roothandle = &(d[u].uid);
return treap :: getRankByValue(argk);
}
return getRankByValue(u<<1) + getRankByValue((u<<1)+1);
}
void modify (int u = 1) {
if(d[u].r < argl || d[u].l > argr) return ;
if(d[u].l == d[u].r) {
argv = treap :: d[d[u].uid].val;
treap :: d[d[u].uid].val = argk;
return ;
}
modify(u<<1), modify((u<<1)+1);
treap :: roothandle = &(d[u].uid);
treap :: erase (treap :: locate(argv, -1));
treap :: insert(argk);
}
int getCnt (int u = 1) {
if(d[u].r < argl || d[u].l > argr ) return 0;
if(d[u].l >= argl && d[u].r <= argr) {
treap :: roothandle = &(d[u].uid);
return treap :: d[treap::locate(argk)].cnt;
}
return getCnt(u<<1) + getCnt((u<<1)+1);
}
int getValueByRank () {
int lef = 0, rig = 100000000, ans = 0;
int tmp1 = argk;
while(lef <= rig) {
int mid = (lef+rig)>>1; argk = mid;
int tmp2 = getRankByValue();
if(tmp2 >= tmp1) rig = mid-1;
else lef = mid+1, ans = mid;
}
return ans;
}
}
inline int getInt () {
int ret = 0; char ch; bool f = false;
while((ch = getchar()) < '0' || ch > '9' ) f |= (ch == '-');
ret = ch - '0';
while((ch = getchar()) >= '0' && ch <= '9') ret *= 10, ret += ch-'0';
return f ? -ret : ret;
}
int src[MAXN];
int main () {
int N = getInt(), M = getInt();
for(int i = 1; i<=N; i++) src[i] = getInt();
treap :: src = ibt :: temp; ibt :: src = src;
ibt :: build(1, N);
for(int i = 1; i<=M; i++) {
int op = getInt(), a, b, c;
if(op == 1) {
a = getInt(), b = getInt(), c = getInt();
ibt :: fillArgs(a, b, c);
printf("%d\n", ibt :: getRankByValue()+1);
} else if(op == 2) {
a = getInt(), b = getInt(), c = getInt();
ibt :: fillArgs(a, b, c);
printf("%d\n", ibt :: getValueByRank());
} else if(op == 3) {
a = getInt(), c = getInt();
ibt :: fillArgs(a, a, c);
ibt :: modify();
} else if(op == 4) {
a = getInt(), b = getInt(), c = getInt();
ibt :: fillArgs(a, b, c);
ibt :: argk = ibt :: getRankByValue();
printf("%d\n", ibt :: getValueByRank());
} else if(op == 5) {
a = getInt(), b = getInt(), c = getInt();
ibt :: fillArgs(a, b, c);
int tmp = ibt :: getRankByValue();
ibt :: fillArgs(a, b, c);
ibt :: argk = tmp + ibt :: getCnt() + 1;
printf("%d\n", ibt :: getValueByRank());
}
}
}
Join the discussion