【题意】求有修改的区间第k大。
【分析】这个题目就是ZOJ2112(BZOJ1901)完全一样的；那个由于询问较少可以树状数组套主席树,树状数组套动态结点线段树,分块等；但是对于这题上面算法都会超内存(树状数组套主席树在G++下是TLE，其实是超内存引起的，HDU这个版本的G++对RE不太敏感)；但是可以用线段树套treap+二分；但是这样时间复杂度为q*logn*logn*logn；空间为n*logn；刚好卡过；
但是有一个更好的方法:整体二分+树状数组。今天才学，其实很简单，知道单个查询在线段树上的二分后就很容易理解整体二分了，无非就是所有查询和修改都同时进行二分；通过二分值域以及把所有当前操作范围分治；分别分入已经完成修改的左边还是等待修改的右边即可；比较难说出来；看代码体会吧。这个时间复杂度为:(q+n)*logn*logn；空间复杂度:n+q；
由于一次查询出所有答案所以常数比n次logn*logai的要小很多；
【AC CODE(线段树套)】5584ms
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 1e5+10;
struct NODE{
NODE *ch[2];
int r, v, sum, cnt;
}node[MAXN*50];
int a[MAXN], mi, mx, tol;
NODE *rt[MAXN<<1];
int cmp(const NODE *a, int x){
if(x == a->v) return -1;
return x<a->v?0:1;
}
void push_up(NODE *u){
u->sum = u->cnt;
if(u->ch[0]) u->sum += u->ch[0]->sum;
if(u->ch[1]) u->sum += u->ch[1]->sum;
}
NODE *newnode(int a){
node[tol].v = a,node[tol].ch[0] = node[tol].ch[1] = NULL, node[tol].r = rand();
node[tol].sum = node[tol].cnt = 1;
return &node[tol++];
}
void clear(NODE* &u)//清空树
{
u = NULL;
}
void rotate(NODE* &u, int d)//旋转，d = 0左旋,d = 1右旋
{
NODE *k = u->ch[d^1];
u->ch[d^1] = k->ch[d], k->ch[d] = u;
push_up(u), push_up(k); //更新sum,先更新u
u = k;
}
void insert(NODE* &u, int v)//插入键值v(不需要保证v是否存在)
{
if(!u) u = newnode(v);
else
{
int d = cmp(u,v);//不要使用cmp(),可能已经存在相同的v
if(-1 == d)//已经存在该点
{
u->cnt++;
u->sum++;
return;
}
insert(u->ch[d], v);
if(u->r < u->ch[d]->r) //如果儿子的r比当前大则需要旋转
rotate(u,d^1);//左儿子则右旋，右儿子左旋
}
push_up(u);//更新sum
}
void del(NODE* &u, int v)//删除键值v
{
int d = cmp(u,v);
if(~d)//没找到继续往下找
del(u->ch[d],v);
else
{
if(u->cnt > 1)
{
u->cnt--;
u->sum--;
return;
}
NODE *o = u;
if(u->ch[0] && u->ch[1])//左右儿子都存在
{
int d2 = u->ch[0]->r > u->ch[1]->r?1:0;//优先级大的儿子旋转为根
rotate(u,d2);
del(u->ch[d2],v);
}
else
{
if(!u->ch[0]) u = u->ch[1];//只有右儿子
else u = u->ch[0];//只有左儿子
//delete o;
//u = NULL;
}
}
if(u) push_up(u);
}
int upper(NODE *u, int v)//v在树中排第几,即有几个<=v
{
if(!u) return 0;
if(v == u->v) return u->cnt+(u->ch[0]?u->ch[0]->sum:0);
if(v < u->v) return upper(u->ch[0], v);
return upper(u->ch[1],v)+(u->ch[0]?u->ch[0]->sum:0)+u->cnt;
}
void pt(NODE *u)
{
if(NULL == u) return;
pt(u->ch[0]);
rep(i,0,u->cnt)
printf("%d\n", u->v);
pt(u->ch[1]);
}
inline int id(int x, int y){return x+y|x!=y;}
void bulid(int x, int y)
{
int u = id(x,y);
clear(rt[u]);
repe(i,x,y) insert(rt[u],a[i]);
if(x == y) return;
int m = (x+y)>>1;
bulid(x,m);
bulid(m+1,y);
}
int tmp;
void update(int x, int y, int p, int v)
{
if(x == y)
{
int u = id(x,y);
tmp = rt[u]->v;
rt[u]->v = v;
return;
}
int m = (x+y)>>1;
if(p <= m) update(x,m,p,v);
else update(m+1,y,p,v);
int u = id(x,y);
del(rt[u],tmp);
insert(rt[u],v);
}
int query(int x, int y, int ql, int qr, int v)
{
if(ql <= x && y <= qr)
{
int u = id(x,y);
return upper(rt[u],v);
}
int m = (x+y)>>1, ans = 0;
if(ql <= m) ans += query(x,m,ql,qr,v);
if(qr > m) ans += query(m+1,y,ql,qr,v);
return ans;
}
int n;
int sloved(int x, int y, int k)
{
int l = mi, r = mx, ans;
while(l <= r)
{
int m = (l+r)>>1;
if(query(0,n-1,x,y,m) >= k)
ans = m, r = m-1;
else l = m+1;
}
return ans;
}
int main()
{
#ifdef SHY
freopen("d:\\1.txt", "r", stdin);
#endif
while(~scanf("%d", &n))
{
int q;
mi = INF, mx = -1;
tol = 0;
rep(i,0,n)
{
scanf("%d%*c", &a[i]);
mi = min(mi,a[i]);
mx = max(mx,a[i]);
}
bulid(0,n-1);
scanf("%d", &q);
while(q--)
{
int op;
scanf("%d", &op);
if(1 == op)
{
int p,v;
scanf("%d %d", &p,&v);
p--;
update(0,n-1,p,v);
mi = min(mi,v);
mx = max(mx,v);
}
else
{
int x,y,k;
scanf("%d %d %d",&x, &y, &k);
x--,y--;
printf("%d\n", sloved(x,y,k));
}
}
}
return 0;
}
【AC CODE(整体二分+树状数组)】421ms
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = (1e5)+10, MAXIN = 1e4,MAXOUT = 1e4;
char buf[MAXIN], *ps = buf, *pe = buf+1;
inline void rnext(){
if(++ps == pe) pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);
}
template <class T>
inline bool in(T &ans)
{
ans = 0;
T f = 1;
if(ps == pe) return false;
do{ rnext(); if('-' == *ps) f = -1;} while(!isdigit(*ps) && ps != pe);
if(ps == pe) return false;
do{ ans = (ans<<1)+(ans<<3)+*ps-48;rnext();}while(isdigit(*ps) && ps != pe);
ans *= f;
return true;
}
char bufout[MAXOUT], outtmp[50],*pout = bufout, *pend = bufout+MAXOUT;
inline void write(){ fwrite(bufout,sizeof(char),pout-bufout,stdout);pout = bufout;}
inline void out_char(char c){ *(pout++) = c;if(pout == pend) write();}
inline void out_str(char *s)
{
while(*s){ *(pout++) = *(s++); if(pout == pend) write(); }
}
template <class T>
inline void out_int(T x) {
if(!x){ out_char('0');return;}
if(x < 0) x = -x,out_char('-');
int len = 0;
while(x){ outtmp[len++] = x%10+48; x /= 10;}
outtmp[len] = 0;
for(int i = 0, j = len-1; i < j; i++,j--) swap(outtmp[i],outtmp[j]);
out_str(outtmp);
}
/*=====================================*/
struct NODE{
int op,x,y,k,id;
}qu[MAXN*3],q1[MAXN*3],q2[MAXN*3];
int a[MAXN],num[MAXN<<1],sum[MAXN],n;
inline int lowbit(int x){return x&-x;}//树状数组维护每个位置区间的数字个数
void update(int x, int v)
{
while(x <= n)
{
sum[x] += v;
x += lowbit(x);
}
}
int query(int x)
{
int ans = 0;
while(x > 0)
{
ans += sum[x];
x -= lowbit(x);
}
return ans;
}
int ans[MAXN];
void sloved(int x, int y, int l, int r)//第[x,y]之间的查询，已经被二分的值域[l,r]
{
if(l == r)
{
repe(i,x,y) if(2 == qu[i].op) ans[qu[i].id] = num[l];
return;
}
int m = (l+r)>>1,c1 = 0,c2 = 0;
repe(i,x,y)//划分[x,y]的操作进入左半值域[l,m]还是右半值域[m+1,r]
{
if(2 == qu[i].op)
{
int d = query(qu[i].y)-query(qu[i].x-1);//[x,y]中在当前查询之前，所要查询的区间中所有<=m的数字个数(循环顺序保证了现在树状数组中保存的都是之前的,且都<=m)
if(qu[i].k <= d) q1[c1++] = qu[i];//如果该查询的左边已经数字个数够了则进入左边
else//左边不够进入右边，由于分治所以k要减去左边的数量d
{
qu[i].k -= d;
q2[c2++] = qu[i];
}
}
else
{
if(qu[i].y <= m)//当前查询<=m进入左边，并更新树状数组
{
update(qu[i].x,qu[i].op);
q1[c1++] = qu[i];
}
else q2[c2++] = qu[i];
}
}
rep(i,0,c1) if(2 != q1[i].op) update(q1[i].x,-q1[i].op);//清空树状数组
memcpy(qu+x,q1,sizeof(NODE)*c1);
memcpy(qu+x+c1,q2,sizeof(NODE)*c2);
sloved(x,x+c1-1,l,m);
sloved(x+c1,y,m+1,r);
}
int main()
{
#ifdef SHY
freopen("d:\\1.txt", "r", stdin);
#endif
while(in(n))
{
int all = 0,tol = 0,query_cnt = 0;
repe(i,1,n)
{
in(a[i]),num[tol++] = a[i];
qu[++all] = {1,i,a[i]};
}
int q,op,x,y,k;
in(q);
rep(i,0,q)
{
in(op);in(x);in(y);
if(2 == op)
{
in(k);
qu[++all] = {2,x,y,k,query_cnt++};
}
else
{
num[tol++] = y;
qu[++all] = {-1,x,a[x]};
qu[++all] = {1,x,y};
a[x] = y;
}
}
sort(num,num+tol);
int cnt = unique(num,num+tol)-num;
repe(i,1,all)
{
if(2 != qu[i].op) qu[i].y = lower_bound(num,num+cnt,qu[i].y)-num;
}
sloved(1,all,0,cnt-1);
rep(i,0,query_cnt) out_int(ans[i]),out_char('\n');
}
write();
return 0;
}
