HDU5412

【题意】求有修改的区间第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;
}