# 42 条题解

• @ 2016-08-21 15:54:54

我知道ls想让我写一个树套树，可是。。
用O(n)的kth算法可以AC为什么写树套树呢？
```c++
测试数据 #0: Accepted, time = 250 ms, mem = 948 KiB, score = 10
测试数据 #1: Accepted, time = 500 ms, mem = 948 KiB, score = 10
测试数据 #2: Accepted, time = 46 ms, mem = 952 KiB, score = 10
测试数据 #3: Accepted, time = 312 ms, mem = 948 KiB, score = 10
测试数据 #4: Accepted, time = 156 ms, mem = 948 KiB, score = 10
测试数据 #5: Accepted, time = 500 ms, mem = 952 KiB, score = 10
测试数据 #6: Accepted, time = 515 ms, mem = 948 KiB, score = 10
测试数据 #7: Accepted, time = 531 ms, mem = 948 KiB, score = 10
测试数据 #8: Accepted, time = 656 ms, mem = 952 KiB, score = 10
测试数据 #9: Accepted, time = 109 ms, mem = 952 KiB, score = 10

Accepted, time = 3575 ms, mem = 952 KiB, score = 100
``` ```c++
#include <bits/stdc++.h>
using namespace std;

int n, q, t;
char c;
int arr[50005], a[50005];

{
int a = 0, c;
do c = getchar(); while (!isdigit(c));
while (isdigit(c)) {
a = a*10+c-'0';
c = getchar();
}
return a;
}

char get()
{
char c;
while (!isalpha(c))
c = getchar();
return c;
}

int kth(int l, int r, int k)
{
for (int i = l; i <= r; i++) arr[i] = a[i];
while (1) {
//cout << l << " " << r << " " << k << endl;
if (l == r) return arr[l];
swap(arr[l], arr[(l+r)>>1]);
int m = l;
for (int i = l+1; i <= r; i++)
if (arr[i] < arr[l])
swap(arr[++m], arr[i]);
swap(arr[l], arr[m]);
// cout << l << " " << r << " " << k << " " << m << endl;
if (k == m) return arr[k];
else if (k <= m) r = m-1;
else l = m+1;
}
}
int main()
{
for (int i = 1; i <= n; i++)
for (int i = 1; i <= q; i++) {
c = get();
int a1, b, d;
if (c == 'Q') {
if (b < a1) swap(a1, b);
printf("%d\n", kth(a1, b, a1+d-1));
} else {
a[a1] = b;
}
}
return 0;
}

• @ 2016-08-21 15:56:22

70行水过，顺便：
Orz会树套树的犇们

• @ 2016-08-21 16:54:58

你这方法真666。。。

• @ 2016-08-26 17:05:38

暴力出奇迹，是OI界永恒不变的真理

• @ 2018-08-17 07:45:13

# Markdown

• @ 2017-07-03 18:45:37
``````#include <bits/stdc++.h>

using namespace std;
const int N = 50010;
typedef unsigned long ul;
typedef int seg[90 * N];
typedef int arr[N];
typedef pair<int, int> pii;
seg lson, rson, c;
arr a, bit;
vector<int> x;
int tot, n, m, xsiz;

struct T {
int p, val, l, r;
char t;
} q[N];

void init_hash() {
sort(x.begin(), x.end());
auto en = unique(x.begin(), x.end());
xsiz = (int) (en - x.begin());
x.resize((ul) xsiz);
}

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

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

void segins(int &i, int l, int r, int p, int del) {
if (i == 0)
i = [&tot]() {
int res = ++tot;
lson[res] = rson[res] = c[res] = 0;
return res;
}();
c[i] += del;
if (l == r) return;
int mid = l + r >> 1;
if (p <= mid) segins(lson[i], l, mid, p, del);
else segins(rson[i], mid + 1, r, p, del);
}

void bitchg(int p, int val, int del) {
while (p <= n) {
segins(bit[p], 1, xsiz, val, del);
p += lowbit(p);
}
}

int bitask(int l, int r, int k) {
vector<pii> v;
auto f = [&v](int x, int del) {
while (x) {
v.push_back(pii(bit[x], del));
x -= lowbit(x);
}
};
auto turn = [&v](int dir) {
transform(v.begin(), v.end(), v.begin(), [dir](pii x) -> pii {
return dir ? pii(rson[x.first], x.second) : pii(lson[x.first], x.second);
});
};
auto getleft = [&v]() {
int tot = 0;
for_each(v.begin(), v.end(), [&tot](pii x) { tot += c[lson[x.first]] * x.second; });
};
f(l - 1, -1);
f(r, 1);
l = 1;
r = xsiz;
while (l < r) {
int mid = l + r >> 1, tmp = getleft();
if (k <= tmp) {
r = mid;
turn(0);
} else {
l = mid + 1;
k = k - tmp;
turn(1);
}
}
return l;
}

int main() {
//int t;
//cin >> t;
//while (t--) {
x.clear();
tot = 0;
cin >> n >> m;
memset(bit, 0, sizeof(int) * (n + 1));
for (int i = 1; i <= n; i++) scanf("%d", a + i), x.push_back(a[i]);
for (int i = 1; i <= m; i++) {
getchar();
q[i].t = (char) getchar();
if (q[i].t == 'C') {
scanf("%d%d", &q[i].p, &q[i].val);
x.push_back(q[i].val);
} else scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].val);
}
init_hash();
transform(a + 1, a + n + 1, a + 1, [](int x) { return hafn(x); });
for (int i = 1; i <= n; i++) bitchg(i, a[i], 1);
for (int i = 1; i <= m; i++)
if (q[i].t == 'C') q[i].val = hafn(q[i].val);
for (int j = 1; j <= m; j++) {
auto i = q[j];
if (i.t == 'C') {
bitchg(i.p, a[i.p], -1);
a[i.p] = i.val;
bitchg(i.p, a[i.p], 1);
} else {
int id = bitask(i.l, i.r, i.val);
printf("%d\n", x[id - 1]);
}
}
//}
return 0;
}
``````

树状数组套线段数哦

• @ 2017-03-04 17:52:10
``````#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
//平衡树套线段树
const int maxst=200005,maxbbt=1000005;
struct bTree {
int father,child[2]; //0左儿子 1右儿子
int key,size; //key为结点属性 size为子树大小
bTree() {}
bTree(int fa,int lc,int rc,int data,int sz):father(fa),key(data),size(sz) {
child[0]=lc,child[1]=rc;
}
};
struct Splay {
bTree tree[maxbbt];
void init() {
memset(tree,0,sizeof(tree));
}
void clear(int index) {
tree[index]=bTree(0,0,0,0,0);
}
int checkson(int index) { //判断是父亲的左儿子还是右儿子
return tree[tree[index].father].child[1]==index;
}
void update(int index) { //更新size
if(!index)return;
tree[index].size=1;
if(tree[index].child[0])tree[index].size+=tree[tree[index].child[0]].size;
if(tree[index].child[1])tree[index].size+=tree[tree[index].child[1]].size;
}
void rotate(int index) { //旋转到根
int father=tree[index].father,grandpa=tree[father].father,side=checkson(index);
tree[father].child[side]=tree[index].child[side^1];
tree[tree[father].child[side]].father=father;
tree[father].father=index;
tree[index].child[side^1]=father;
tree[index].father=grandpa;
if(grandpa)tree[grandpa].child[tree[grandpa].child[1]==father]=index;
update(father);
update(index);
}
void splay(int& root,int index) {
if(index==root)return;
for(int father; (father=tree[index].father); rotate(index)) //基本旋转
if(tree[father].father)rotate((checkson(index)==checkson(father))?father:index); //附加旋转
root=index;
}
void insert(int& root,int index,int v) {
if(!root) {
root=index;
tree[index]=bTree(0,0,0,v,1);
return;
}
int now=root,father=0;
while(true) {
father=now; //保存父亲
now=tree[now].child[tree[now].key<v]; //往哪边走
if(!now) {
tree[index]=bTree(father,0,0,v,1);
tree[father].child[tree[father].key<v]=index;
update(father);
splay(root,index);
break;
}
}
}
void remove(int& root) { //删除根
if(!tree[root].child[0]||!tree[root].child[1]) { //只有左右儿子
int oldroot=root;
root=tree[root].child[tree[root].child[0]==0];
tree[root].father=0;
clear(oldroot);
return;
}
int pre=inline_pre_next(root,0),oldroot=root;
splay(root,pre); //伸展前驱
tree[tree[oldroot].child[1]].father=root; //将原根右子树接到根上（相当于删除了）
tree[root].child[1]=tree[oldroot].child[1];
clear(oldroot);
update(root);
}
int inline_pre_next(int& root,int bj) {
int now=tree[root].child[bj];
while(tree[now].child[bj^1])now=tree[now].child[bj^1];
return now;
}
int find(int& root,int rank) { //在root为根的树中找到排名为rank的点，返回下标
int now=root;
while(true) {
if(rank<=0||now<=0)return -1; //找不到
if(tree[now].child[0]&&rank<=tree[tree[now].child[0]].size)now=tree[now].child[0];
else {
int tmp=(tree[now].child[0]?tree[tree[now].child[0]].size:0)+1;
if(rank<=tmp)return now;
rank-=tmp;
now=tree[now].child[1];
}
}
}
} bbt;
int n;
struct sTree {
int left,right,root; //记录对应平衡树编号
sTree() {}
sTree(int l,int r,int roo):left(l),right(r),root(roo) {}
};
struct Segment_Tree {
sTree tree[maxst];
void init() {
memset(tree,0,sizeof(tree));
bbt.init();
}
void build(int index,int depth,int Left,int Right,int* a) {
tree[index]=sTree(Left,Right,0);
if(Left==Right) { //叶子节点
bbt.insert(tree[index].root,(depth-1)*n+Left,a[Left]); //对应编号（类似分层图）
return;
}
int mid=(Left+Right)>>1;
build(index<<1,depth+1,Left,mid,a);
build((index<<1)|1,depth+1,mid+1,Right,a);
for(int i=Left; i<=Right; i++)bbt.insert(tree[index].root,(depth-1)*n+i,a[i]); //路径上的都要建
}
void modify(int index,int depth,int pos,int v) {
int M=(depth-1)*n+pos; //计算出平衡树中编号
bbt.splay(tree[index].root,M);
bbt.remove(tree[index].root);
bbt.insert(tree[index].root,M,v);
int l=tree[index].left,r=tree[index].right;
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid)modify(index<<1,depth+1,pos,v);
else modify((index<<1)|1,depth+1,pos,v);
}
int query(int index,int Left,int Right,int v) { //统计比v小的个数
if(tree[index].right<Left||tree[index].left>Right)return 0;
if(Left<=tree[index].left&&Right>=tree[index].right) { //完全包含
int Now=tree[index].root,sum=0;
while(Now) {
if(bbt.tree[Now].key<v)sum+=bbt.tree[bbt.tree[Now].child[0]].size+1;
Now=bbt.tree[Now].child[bbt.tree[Now].key<v];
}
return sum;
}
return query(index<<1,Left,Right,v)+query((index<<1)|1,Left,Right,v);
}
int find(int Left,int Right,int rank) { //寻找第rank小的数
int Now=tree[1].root,ans=0;
if(Left==1&&Right==n)return bbt.tree[bbt.find(Now,rank)].key; //特殊情况
while(Now) { //二分查找
if(query(1,Left,Right,bbt.tree[Now].key)<=rank-1) {
ans=bbt.tree[Now].key;
Now=bbt.tree[Now].child[1];
} else Now=bbt.tree[Now].child[0];
}
return ans;
}
} st;
int m,a[50005];
int main() {
n=Get_Int();
m=Get_Int();
st.init();
for(int i=1; i<=n; i++)a[i]=Get_Int();
st.build(1,1,1,n,a);
for(int i=1; i<=m; i++) {
char order='a';
while(order!='C'&&order!='Q')order=getchar();
int x=Get_Int(),y=Get_Int();
if(order=='Q') {
int val=Get_Int();
printf("%d\n",st.find(x,y,val));
} else st.modify(1,1,x,y);
}
return 0;
}
``````
• @ 2016-04-19 19:45:31

以此纪念我的第一个树套树：

测试数据 #0: Accepted, time = 250 ms, mem = 21704 KiB, score = 10
测试数据 #1: Accepted, time = 359 ms, mem = 21708 KiB, score = 10
测试数据 #2: Accepted, time = 78 ms, mem = 21708 KiB, score = 10
测试数据 #3: Accepted, time = 296 ms, mem = 21712 KiB, score = 10
测试数据 #4: Accepted, time = 234 ms, mem = 21704 KiB, score = 10
测试数据 #5: Accepted, time = 406 ms, mem = 21708 KiB, score = 10
测试数据 #6: Accepted, time = 437 ms, mem = 21716 KiB, score = 10
测试数据 #7: Accepted, time = 343 ms, mem = 21708 KiB, score = 10
测试数据 #8: Accepted, time = 453 ms, mem = 21704 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 21708 KiB, score = 10
Accepted, time = 2996 ms, mem = 21716 KiB, score = 100

``````#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
//data默认为int类型，如果要进行修改，请定义新的类型，并重载比较运算符
struct DATA{
int x;
DATA (int t){
x=t;
}
DATA (){}
};
bool operator < (const DATA a,const DATA b){
return a.x<b.x;
}
bool operator > (const DATA a,const DATA b){
return a.x>b.x;
}
bool operator == (const DATA a,const DATA b){
return a.x==b.x;
}
bool operator != (const DATA a,const DATA b){
return a.x!=b.x;
}
struct data_class{
int HASH;
DATA data;
data_class(int h,DATA d){
HASH=h;data=d;
}
data_class(){}
};
bool operator < (const data_class a,const data_class b){
return (a.data<b.data||a.data==b.data&&a.HASH<b.HASH);
}
bool operator > (const data_class a,const data_class b){
return (a.data>b.data||a.data==b.data&&a.HASH>b.HASH);
}
bool operator == (const data_class a,const data_class b){
return a.data==b.data&&a.HASH==b.HASH;
}
bool operator >= (const data_class a,const data_class b){
return a>b||a==b;
}
struct sbt
{
int left,right,size;
data_class data;
sbt(){
left=right=0;
size=0;
}
};
sbt tree[1000000];
int top;
struct SBT{
public:
int root;
SBT(){
root=0;
}
int datacmp(const data_class a,const data_class b){
if (a.data<b.data) return 1;
if (a.data>b.data) return -1;
return 0;
}
tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
}
DATA getDATA(int n){
return tree[n].data.data;
}
void left_rot(int &x){
int y=tree[x].right;
tree[x].right=tree[y].left;
tree[y].left=x;
tree[y].size=tree[x].size;
x=y;
}
void right_rot(int &x){
int y=tree[x].left;
tree[x].left=tree[y].right;
tree[y].right=x;
tree[y].size=tree[x].size;
x=y;
}
void Maintain(int &x,bool flag){
if (!flag){
if (tree[tree[tree[x].left].left].size>tree[tree[x].right].size)
right_rot(x);
else
if (tree[tree[tree[x].left].right].size>tree[tree[x].right].size)
left_rot(tree[x].left),right_rot(x);
else
return;
}
else{
if (tree[tree[tree[x].right].right].size>tree[tree[x].left].size)
left_rot(x);
else
if (tree[tree[tree[x].right].left].size>tree[tree[x].left].size)
right_rot(tree[x].right),left_rot(x);
else
return;
}
Maintain(tree[x].left,0);
Maintain(tree[x].right,1);
Maintain(x,1);
Maintain(x,0);
}
void insert(int &x,data_class data){
if (x==0){
x=++top;
tree[x].size=1;
tree[x].left=tree[x].right=0;
tree[x].data=data;
}
else{
tree[x].size++;
if (data<tree[x].data) insert(tree[x].left,data);
else insert(tree[x].right,data);
Maintain(x,data>=tree[x].data);
}
}
int remove(int fa,int &x,data_class data){
if (!x) return 0;
tree[x].size--;
if (datacmp(data,tree[x].data)==-1)
remove(x,tree[x].right,data);
else
if (datacmp(data,tree[x].data)==1)
remove(x,tree[x].left,data);
else{
if (tree[x].left!=0&&tree[x].right==0){
tree[x]=tree[tree[x].left];
return x;
}
else
if (tree[x].right!=0&&tree[x].left==0){
tree[x]=tree[tree[x].right];
return x;
}
else
if (tree[x].left==0&&tree[x].right==0){
if (root==x) root=0;
if (fa)
if (tree[fa].left==x) tree[fa].left=0;
else tree[fa].right=0;
}
else{
int ret=tree[x].right;
while (tree[ret].left)
ret=tree[ret].left;
tree[x].data=tree[ret].data;
remove(x,tree[x].right,tree[ret].data);
}
}
}
data_class select(int &x,int k){
int r=tree[tree[x].left].size+1;
if (k<r) return select(tree[x].left,k);
else
if (k>r) return select(tree[x].right,k-r);
else
return tree[x].data;
}
int rank(int &x,data_class data){
if (x==0) return 0;
if (data>tree[x].data) return tree[tree[x].left].size+1+rank(tree[x].right,data);
else
if (data<tree[x].data) return rank(tree[x].left,data);
else
return tree[tree[x].left].size+1;
}
//插入一个数
void Insert(int data){
insert(root,data_class(top+1,data));
}
//删除一个数，在相同的情况下，任意删除其中一个
void Remove(int data){
remove(0,root,data_class(0,data));
}
//查询第k小的数字
DATA Select(int k){
return select(root,k).data;
}
//查询比data小（严格）的数字有多少个
int Rank(int data){
return rank(root,data_class(-1,data));
}
//查找data是否存在
bool Find(int data){
if (!root) return 0;
else {
int x=root;
while (tree[x].data.data!=data&&x){
if (tree[x].data.data<data) x=tree[x].right;
else x=tree[x].left;
}
if (!x) return 0;
else if (tree[x].data.data==data) return 1;
}
}
//统计data一共有多少个
int Count(int data){
bool exi=Find(data);
if (exi){
int aaa=Rank(data);
int bbb=Rank(data+1);
return bbb-aaa;
}
else return 0;
}
};
struct INTERVAL_DATA{
int left,right;
SBT SET;
INTERVAL_DATA(){
left=right=0;
}
};
int st[10000],TOP=-1;
struct INTERVAL_TREE{
int n;
INTERVAL_DATA *tree;
INTERVAL_TREE(int height){
tree=new INTERVAL_DATA[2<<height];
n=height;

int h=0;
tree[0].left=0;tree[0].right=(1<<n)-1;
for (int i=0;i<((1<<n)-1);i++){
if (i>(2<<h)-2) h++;
tree[i*2+1].left=tree[i].left;
tree[i*2+2].left=(1<<(n-h-1))|tree[i].left;
tree[i*2+1].right=tree[i*2+1].left+(1<<(n-h-1))-1;
tree[i*2+2].right=tree[i*2+2].left+(1<<(n-h-1))-1;
}
tree[0].left++;tree[0].right++;
for (int i=0;i<(1<<n)-1;i++){
tree[i*2+1].left++;tree[i*2+1].right++;
tree[i*2+2].left++;tree[i*2+2].right++;
}
}
index+=(1<<n)-2;
while (index){
tree[index].SET.Insert(x);
index=(index-1)>>1;
}
tree[0].SET.Insert(x);
}
void change(int index,int y){
index+=(1<<n)-2;
int x=tree[index].SET.getDATA(tree[index].SET.root).x;
while (index){
tree[index].SET.Remove(x);
tree[index].SET.Insert(y);
index=(index-1)>>1;
}
tree[0].SET.Remove(x);
tree[0].SET.Insert(y);
}
void getinterval(int root,int l,int r){
if (tree[root].left==l&&tree[root].right==r) st[++TOP]=root;
else {
int mid=(tree[root].left+tree[root].right)/2;
if (r<=mid) getinterval(root*2+1,l,r);
else if (l>mid) getinterval(root*2+2,l,r);
else {
getinterval(root*2+1,l,mid);
getinterval(root*2+2,mid+1,r);
}
}
}
} a(16);
void shownode(int x){
cout<<tree[x].data.data.x<<' ';
if (tree[x].left) shownode(tree[x].left);
if (tree[x].right) shownode(tree[x].right);
}
void show(SBT x){
shownode(x.root);
cout<<endl;
}
int getans(int I,int J,int K){
TOP=-1;
K--;
a.getinterval(0,I,J);

int Max=1000000000,Min=-1,tmp=0,RANK;
while (Max-Min>1){
tmp=(Max+Min)/2;
RANK=0;
for (int i=0;i<=TOP;i++)
RANK+=a.tree[st[i]].SET.Rank(tmp);
if (RANK<=K) Min=tmp;
else Max=tmp;
}
return Min;
}
int main(){
int n,m,tmp;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d",&tmp);
}

char ord[3];
int I,J,K;
for (int i=1;i<=m;i++){
scanf("%s",ord);
if (ord[0]=='Q'){
scanf("%d%d%d",&I,&J,&K);
cout<<getans(I,J,K)<<endl;
}
else {
scanf("%d%d",&I,&J);
a.change(I,J);
}
}
return 0;
}
``````
• @ 2016-04-09 19:24:17

貌似不允许在讨论区发题解（防止剧透？） (。_。)

• @ 2015-02-07 15:26:04

由于懒得离散化....
树状数组套动态开点的线段树...
不论卡内存还是卡时间都特别紧.......
还好水过了......

PS: 时限是5s?????

Accepted, time = 281 ms, mem = 160984 KiB, score = 10
Accepted, time = 453 ms, mem = 160980 KiB, score = 10
Accepted, time = 78 ms, mem = 160984 KiB, score = 10
Accepted, time = 281 ms, mem = 160984 KiB, score = 10
Accepted, time = 234 ms, mem = 160984 KiB, score = 10
Accepted, time = 468 ms, mem = 160984 KiB, score = 10
Accepted, time = 468 ms, mem = 160980 KiB, score = 10
Accepted, time = 343 ms, mem = 160988 KiB, score = 10
Accepted, time = 468 ms, mem = 160984 KiB, score = 10
Accepted, time = 125 ms, mem = 160988 KiB, score = 10

代码百把行....相当于打个树链剖分...

## Code

const int INF=(1<<30)-1;

int n;
struct node*nil;
struct node
{
int v; //total
node*l,*r;
void update()
{ v=l->v+r->v; }
}pool[13000000];
node*nt=pool;
node*newnode()
{
nt->l=nt->r=nil;
nt->v=0;
return nt++;
}

int cp,cv;

//Sub segment trees
struct SegmentTree
{
node*root;

node*Change(node*x,int l=0,int r=INF)
{
if(cp<l || r<cp) return x;
if(x==nil) x=newnode();
if(l==r) { x->v+=cv; return x; }
int mid=avg(l,r);
x->l=Change(x->l,l,mid);
x->r=Change(x->r,mid+1,r);
x->update();
return x;
}

void Set(int p,int v)
{
if(root<pool) root=nil;
cp=p;
cv=v;
root=Change(root);
}
};

//original segment tree
//performed as tree array

#define bt(x) (x&-x)

int a[1000000]; //this array must be stay here....
SegmentTree t[1000000];
void Change(int p,int s,int v) //location of point, value of point, delete or add in.
{ for(int i=p;i<=n;i+=bt(i)) t[i].Set(s,v); }

node*c[1000];

int Query(int l,int r,int k) //find the element which is rank k.
{

for(int i=r;i>0;i-=bt(i))

for(int i=l-1;i>0;i-=bt(i))
c[ct++]=t[i].root;

l=0,r=INF;
while(l!=r)
{
//for(int i=0;i<ct;i++)
//cout<<c[i]<<' '; cout<<endl; cout<<l<<' '<<r<<endl; cout<<endl;

int mid=avg(l,r);
int clv=0; //current node's left node count.

clv+=c[i]->l->v;
clv-=c[i]->l->v;

if(k<=clv) //the element we want find is on the left block
{
for(int i=0;i<ct;i++)
c[i]=c[i]->l;
r=mid;
}
else
{
for(int i=0;i<ct;i++)
c[i]=c[i]->r;
k-=clv;
l=mid+1;
}
}

return l;
}

int q;

int main()
{
nil=newnode();
nil->l=nil->r=nil;
nil->v=0;

n=getint();
q=getint();
for(int i=0;i<n;i++)
Change(i+1,a[i+1]=getint(),1);

for(int i=0;i<q;i++)
{
char c[5];
scanf("%s",c);
if(c[0]=='C')
{
int i=getint();
int v=getint();
Change(i,a[i],-1);
Change(i,a[i]=v,1);
}
else
{
int i=getint();
int j=getint();
int k=getint();
printf("%d\n",Query(i,j,k));
}
}

return 0;
}

• @ 2014-10-09 09:19:54

主席树随便搞？

• @ 2014-03-14 14:20:15

线段树套treap也可做
一开始试了一下线段树套Splay，不知道是写萎了还是什么...TLE了很久...

• @ 2013-10-16 18:57:13

树状数组套主席树：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

#define MAXN 50001
#define lowbit(x)(((~(x))+1)&x)
#define MAXM 10001
#define For(i,x) for (int i=x;i;i-=lowbit(i))
#define Rep(i,x) for (int i=x;i<=n;i+=lowbit(i))
#define MAXT 20

void getint(int &t) {
scanf("%d",&t);
}

void putint(int t) {
printf("%d\n",t);
}

struct saver {
int v,t;
} num[MAXN+MAXM];
int R[MAXN+MAXM],C[MAXN+MAXM],RN=0;

bool cmp(saver x,saver y) {
return x.v<y.v;
}

int a[MAXN];
int Query[MAXM][4];
int n,m,V=0;

struct node {
int s;
int left,right;
node () {
s=left=right=0;
}
} Node[MAXN*MAXT*MAXT];

int T[MAXN];
int M=0;

void build(int l,int r,int &t) {
if (!t) t=++M;
if (l==r) return ;
int mid=(l+r)>>1;
build(l,mid,Node[t].left),build(mid+1,r,Node[t].right);
}

void Add(int x,int y,int l,int r,int u,int t) {
Node[t].s=Node[u].s+y;
if (l==r) return ;
int mid=(l+r)>>1;
if (x<=mid) {
Node[t].right=Node[u].right;
} else {
Node[t].left=Node[u].left;
}
}

void INIT() {
getint(n),getint(m);
for (int i=0;i++<n;) {
getint(a[i]);
num[++V].v=a[i];
num[V].t=i;
}
for (int i=0;i++<m;) {
int c;
while (1) {
c=getchar();
if (c==int('Q')||c==int('C')) break;
}
if (c==int('Q')) {
Query[i][0]=1;
getint(Query[i][1]),getint(Query[i][2]),getint(Query[i][3]);
} else {
Query[i][1]=0;
getint(Query[i][1]),getint(Query[i][2]);
num[++V].v=Query[i][2];
num[V].t=n+i;
}
}
sort(num+1,num+V+1,cmp);
C[++RN]=num[1].v,R[num[1].t]=1;
for (int i=1;i++<V;) {
if (num[i].v!=num[i-1].v) {
C[++RN]=num[i].v;
}
R[num[i].t]=RN;
}
memset(T,0,sizeof(T));
build(1,RN,T[0]);
for (int i=0;i++<n;) {
int p=T[0];
for (int j=i-lowbit(i);j++<i;) {
p=T[i];
}
}
}

int t1[MAXT],t2[MAXT];
int n1,n2,sum;

void Solve() {
for (int i=0;i++<m;) {
if (!Query[i][0]) {
int p;
Rep(j,Query[i][1]) {
T[j]=p;
}
Rep(j,Query[i][1]) {
T[j]=p;
}
R[Query[i][1]]=R[n+i];
} else {
n1=n2=0;
For(j,Query[i][2]) t1[++n1]=T[j];
For(j,Query[i][1]-1) t2[++n2]=T[j];
int l=1,r=RN;
while (l!=r) {
sum=0;
for (int j=0;j++<n1;) sum+=Node[Node[t1[j]].left].s;
for (int j=0;j++<n2;) sum-=Node[Node[t2[j]].left].s;
if (sum>=Query[i][3]) {
r=(l+r)>>1;
for (int j=0;j++<n1;) t1[j]=Node[t1[j]].left;
for (int j=0;j++<n2;) t2[j]=Node[t2[j]].left;
} else {
Query[i][3]-=sum;
l=((l+r)>>1)+1;
for (int j=0;j++<n1;) t1[j]=Node[t1[j]].right;
for (int j=0;j++<n2;) t2[j]=Node[t2[j]].right;
}
}
putint(C[l]);
}
}
}

int main() {
INIT();
Solve();
return 0;
}

• @ 2013-09-14 11:12:06

树状数组套函数式线段树+离散化
时间复杂度：O((n+m)log(n+m)+(n+m)log^2(n+m))

编译成功

测试数据 #0: Accepted, time = 187 ms, mem = 158932 KiB, score = 10
测试数据 #1: Accepted, time = 312 ms, mem = 158940 KiB, score = 10
测试数据 #2: Accepted, time = 31 ms, mem = 158932 KiB, score = 10
测试数据 #3: Accepted, time = 109 ms, mem = 158936 KiB, score = 10
测试数据 #4: Accepted, time = 93 ms, mem = 158936 KiB, score = 10
测试数据 #5: Accepted, time = 203 ms, mem = 158936 KiB, score = 10
测试数据 #6: Accepted, time = 218 ms, mem = 158932 KiB, score = 10
测试数据 #7: Accepted, time = 140 ms, mem = 158936 KiB, score = 10
测试数据 #8: Accepted, time = 218 ms, mem = 158936 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 158936 KiB, score = 10
Accepted, time = 1542 ms, mem = 158940 KiB, score = 100

• @ 2013-08-20 22:01:55

树状数组+SBT+二分查找O(n log^2 n + m log^3 m)弱弱AC......

编译成功

foo.cpp: In function 'int main()':
foo.cpp:220:16: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1]' [-Wformat]
测试数据 #0: Accepted, time = 562 ms, mem = 11920 KiB, score = 10
测试数据 #1: Accepted, time = 859 ms, mem = 17052 KiB, score = 10
测试数据 #2: Accepted, time = 93 ms, mem = 3120 KiB, score = 10
测试数据 #3: Accepted, time = 531 ms, mem = 9072 KiB, score = 10
测试数据 #4: Accepted, time = 421 ms, mem = 8436 KiB, score = 10
测试数据 #5: Accepted, time = 765 ms, mem = 17108 KiB, score = 10
测试数据 #6: Accepted, time = 812 ms, mem = 18616 KiB, score = 10
测试数据 #7: Accepted, time = 593 ms, mem = 10728 KiB, score = 10
测试数据 #8: Accepted, time = 796 ms, mem = 15896 KiB, score = 10
测试数据 #9: Accepted, time = 156 ms, mem = 3684 KiB, score = 10
Accepted, time = 5588 ms, mem = 18616 KiB, score = 100
#include <cstdio>
#include <cstring>

using namespace std;

#define MAXN 50001

struct node {
int key,s;
node *left,*right;
};

node* t[MAXN];
node* R[MAXN];
node *bank=new(node);

int a[MAXN];
int n,m;

int lowbit(int x){
return ((~x)+1)&x;
}

//--------------Size_Balanced_Tree------------------

int left_ratote(node* &t){
node *k=(*t).right;
(*t).right=(*k).left;
(t).s=((t).left).s+((*t).right).s+1;
(*k).left=t;
(*k).s=(t).s+((*k).right).s+1;
t=k;
return 0;
}

int right_ratote(node* &t){
node *k=(*t).left;
(*t).left=(*k).right;
(t).s=((t).left).s+((*t).right).s+1;
(*k).right=t;
(k).s=((*k).left).s+(*t).s+1;
t=k;
return 0;
}

int maintain(node* &t){
if ((((t).left).left).s>((*t).right).s){
right_ratote(t);
maintain((t).right);
maintain(t);
return 0;
}
if ((
(*(t).left).right).s>((*t).right).s){
left_ratote((*t).left);
right_ratote(t);
maintain((*t).left);
maintain((t).right);
maintain(t);
return 0;
}
if ((
(*(t).right).right).s>((*t).left).s){
left_ratote(t);
maintain((t).left);
maintain(t);
return 0;
}
if ((
(*(t).right).left).s>((*t).left).s){
right_ratote((*t).right);
left_ratote(t);
maintain((*t).left);
maintain((*t).right);
return 0;
}
return 0;
}

int INSERT(int key,node* &t){
if (t==bank){
t=new(node);
(*t).left=(*t).right=bank;
(*t).s=1;
(*t).key=key;
return 0;
}
(*t).s++;
if (key<=(*t).key){
INSERT(key,(*t).left);
} else INSERT(key,(*t).right);
maintain(t);
return 0;
}

int DELETE(int key,node* &t){
if (key==(*t).key){
if ((*t).left==bank&&(*t).right==bank){
delete(t);
t=bank;
return 0;
}
if ((*t).left==bank){
node *p=(*t).right;
delete(t);
t=p;
return 0;
}
if ((*t).right==bank){
node *p=(*t).left;
delete(t);
t=p;
return 0;
}
right_ratote(t);
DELETE(key,(*t).right);
(t).s=((t).left).s+((*t).right).s+1;
maintain(t);
return 0;
}
if (key<(*t).key){
DELETE(key,(*t).left);
} else DELETE(key,(*t).right);
(t).s=((t).left).s+((*t).right).s+1;
return 0;
}

int get_rank(int key,node *t){
int rec=0;
node *p=t;
while (p!=bank){
if ((p).key<key){
rec+=((
(*p).left).s+1);
p=(*p).right;
} else {
p=(*p).left;
}
}
return rec;
}

//----------------Binary_Search--------------------

node *range[MAXN];
int rm;

int GET_RANK(int key){
int rec=0;
for (int i=0;i++<rm;){
rec+=get_rank(key,range[i]);
}
return rec;
}

int get_ans(int l,int r,int k){
rm=0;
int i=r;
while (i>=l){
int s=i-lowbit(i)+1;
if (s>=l){
range[++rm]=t[i];
i=s-1;
} else {
range[++rm]=R[i];
i--;
}
}
int left=-0x7fffffff,right=0x7fffffff;
for (i=0;i++<rm;){
node *p=range[i];
while (p!=bank){
if ((*p).key<left){
p=(*p).right;
continue;
}
if ((*p).key>right){
p=(*p).left;
continue;
}
int s=GET_RANK((*p).key);
if (s==k-1){
return (*p).key;
}
if (s<k-1){
left=(*p).key;
p=(*p).right;
} else {
right=(*p).key;
p=(*p).left;
}
}
}
return left;
}

//----------------------------------------------

int main(){
(*bank).s=0;
(*bank).left=(*bank).right=bank;
scanf("%d%d",&n,&m);
for (int i=0;i++<n;){
scanf("%d",&a[i]);
t[i]=R[i]=bank;
for (int j=i-lowbit(i);j++<i;){
INSERT(a[j],t[i]);
}
INSERT(a[i],R[i]);
}
while (m--){
char c[1];
scanf("%s",&c);
if (c[0]=='Q'){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",get_ans(l,r,k));
} else {
int x,y;
scanf("%d%d",&x,&y);
int i=x;
while (i<=n){
DELETE(a[x],t[i]);
INSERT(y,t[i]);
i+=lowbit(i);
}
(*R[x]).key=y;
a[x]=y;
}
}
return 0;
}

• @ 2013-08-06 22:34:25

这时限。。。这数据。。。直接暴力过。。冷掉~
测试数据 #0: Accepted, time = 3062 ms, mem = 824 KiB, score = 10
测试数据 #1: Accepted, time = 6062 ms, mem = 828 KiB, score = 10
测试数据 #2: Accepted, time = 250 ms, mem = 820 KiB, score = 10
测试数据 #3: Accepted, time = 3109 ms, mem = 828 KiB, score = 10
测试数据 #4: Accepted, time = 1937 ms, mem = 832 KiB, score = 10
测试数据 #5: Accepted, time = 5781 ms, mem = 828 KiB, score = 10
测试数据 #6: Accepted, time = 5796 ms, mem = 832 KiB, score = 10
测试数据 #7: Accepted, time = 5015 ms, mem = 820 KiB, score = 10
测试数据 #8: Accepted, time = 7296 ms, mem = 832 KiB, score = 10
测试数据 #9: Accepted, time = 812 ms, mem = 824 KiB, score = 10
Accepted, time = 39120 ms, mem = 832 KiB, score = 100
代码就免了。。。。直接STL排序

• @ 2013-08-06 22:34:15

这时限。。。这数据。。。直接暴力过。。冷掉~
测试数据 #0: Accepted, time = 3062 ms, mem = 824 KiB, score = 10
测试数据 #1: Accepted, time = 6062 ms, mem = 828 KiB, score = 10
测试数据 #2: Accepted, time = 250 ms, mem = 820 KiB, score = 10
测试数据 #3: Accepted, time = 3109 ms, mem = 828 KiB, score = 10
测试数据 #4: Accepted, time = 1937 ms, mem = 832 KiB, score = 10
测试数据 #5: Accepted, time = 5781 ms, mem = 828 KiB, score = 10
测试数据 #6: Accepted, time = 5796 ms, mem = 832 KiB, score = 10
测试数据 #7: Accepted, time = 5015 ms, mem = 820 KiB, score = 10
测试数据 #8: Accepted, time = 7296 ms, mem = 832 KiB, score = 10
测试数据 #9: Accepted, time = 812 ms, mem = 824 KiB, score = 10
Accepted, time = 39120 ms, mem = 832 KiB, score = 100
代码就免了。。。。直接STL排序

• @ 2012-11-04 14:24:47

├ 测试数据 01：答案正确... (1681ms, 6460KB)

├ 测试数据 02：答案正确... (2664ms, 7436KB)

├ 测试数据 03：答案正确... (464ms, 5676KB)

├ 测试数据 04：答案正确... (2461ms, 6848KB)

├ 测试数据 05：答案正确... (1556ms, 6848KB)

├ 测试数据 06：答案正确... (2742ms, 7436KB)

├ 测试数据 07：答案正确... (2570ms, 7628KB)

├ 测试数据 08：答案正确... (3334ms, 7044KB)

├ 测试数据 09：答案正确... (3678ms, 7436KB)

├ 测试数据 10：答案正确... (1447ms, 6652KB)

表示快排改一下也可以做……（好像也慢不了多少啊）

附上代码：

type arr=array[0..50001] of longint;

var a:arr;

l,r,n,m,i,j,k,pos,w:longint;

x:char;

function sort(t,w:longint; a:arr):longint;

var i,j,mid,o:longint;

begin

i:=t; j:=w; mid:=a[(i+j) shr 1];

repeat

while a[i]mid do dec(j);

if ij;

if k=i-(l-1) then exit(sort(i,w,a)) else

exit(mid);

end;

begin

for i:=1 to m do

begin

if x='Q' then

begin

writeln(sort(l,r,a));

end;

if x='C' then

begin

a[pos]:=w;

end;

end;

end.

• @ 2010-07-09 18:16:39

编译通过...

├ 测试数据 01：答案正确... 618ms

├ 测试数据 02：答案正确... 976ms

├ 测试数据 03：答案正确... 25ms

├ 测试数据 04：答案正确... 664ms

├ 测试数据 05：答案正确... 415ms

├ 测试数据 06：答案正确... 867ms

├ 测试数据 07：答案正确... 883ms

├ 测试数据 08：答案正确... 898ms

├ 测试数据 09：答案正确... 1054ms

├ 测试数据 10：答案正确... 290ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：6690ms

2010-7-9 评测机：6K

线段树套SBT M*lg^2N*lg(10^9) 140行

速度被lx神牛BS了...

• @ 2010-07-03 13:52:33

编译通过...

├ 测试数据 01：答案正确... 2556ms

├ 测试数据 02：答案正确... 4244ms

├ 测试数据 03：答案正确... 666ms

├ 测试数据 04：答案正确... 3572ms

├ 测试数据 05：答案正确... 2291ms

├ 测试数据 06：运行超时|格式错误...

├ 测试数据 07：答案正确... 4025ms

├ 测试数据 08：答案正确... 4916ms

├ 测试数据 09：答案正确... 5275ms

├ 测试数据 10：运行超时|格式错误...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：80 有效耗时：27545ms

我疯了 vijos mini 这么卡。。。。r~！

• @ 2010-04-10 11:08:04

delete:=key[t];

if (left[t]=0)or(right[t]=0) then t:=left[t]+right[t]

else key[t]:=delete(left[t],v);

忘了写key[t]:=调了很多数据都没发现，

还有就是排序写好后忘了把sort（1，rr）写上去（就是没掉用）

我用的是树套树，写到一半才想到树状数组+SBT

听SWJ神牛说还可以用离散化+二分（这个问题的解是谁）+二维树状数组+hash，

就是（x，y）表示1-x的区间内1-y的和（离散化后重新编号，暴力赋值（像计数排序））。每次用求x-y的小于k有多少个时，分别求1-x-1，和1-y。

• @ 2010-04-04 18:35:55

树状数组+SBT 200 行

悲剧的碰上 vag 6K

编译通过...

├ 测试数据 01：答案正确... 306ms

├ 测试数据 02：答案正确... 493ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 352ms

├ 测试数据 05：答案正确... 181ms

├ 测试数据 06：答案正确... 555ms

├ 测试数据 07：答案正确... 555ms

├ 测试数据 08：答案正确... 602ms

├ 测试数据 09：答案正确... 540ms

├ 测试数据 10：答案正确... 150ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3734ms

• @ 2009-10-25 20:48:01

纯线段树不行么？

ID
1665

7

(无)

660

111

17%

3