1. 题目

2. 题解

以前写过一个树套树的题解QvQ:传送门= ̄ω ̄=

这次用整体二分做,快得飞起啊23333~

有先决科技点:整体二分解决静态区间kth问题:传送门= ̄ω ̄=

看懂上面的那个问题了的话这个问题就很好办了。

把每个修改操作拆成一个删除操作和一个添加操作即可,别的和上面那个问题一模一样。

代码:

#include <bits/stdc++.h>
#define NS (50005)
#define MS (10005)
#define lowbit(a) (a&-a)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct query{int l,r,k,id,type;}Q[NS+(MS<<1)],Q1[NS+(MS<<1)],Q2[NS+(MS<<1)];
int T,n,m,cnt,data[NS],qcnt,ans[MS],t[NS];
char opt[5];
void add(int pos,int d){for(;pos<=n;pos+=lowbit(pos))t[pos]+=d;}
int sum(int pos){int tmp=0;for(;pos;pos-=lowbit(pos))tmp+=t[pos];return tmp;}
void binary(int QL,int QR,int l,int r)
{
    if(QL>QR)return;
    if(l==r){for(int i=QL;i<=QR;i++)if(Q[i].type==2)ans[Q[i].id]=l;return;}
    int mid=(l+r)>>1,x1=0,x2=0;
    for(int i=QL,tmp;i<=QR;i++)
        if(!Q[i].type)
        {
            if(Q[i].k<=mid)add(Q[i].id,1),Q1[++x1]=Q[i];
            else Q2[++x2]=Q[i];
        }
        else if(Q[i].type==1)
        {
            if(Q[i].k<=mid)add(Q[i].id,-1),Q1[++x1]=Q[i];
            else Q2[++x2]=Q[i];
        }
        else
        {
            tmp=sum(Q[i].r)-sum(Q[i].l-1);
            if(Q[i].k<=tmp)Q1[++x1]=Q[i];
            else Q2[++x2]=Q[i],Q2[x2].k-=tmp;
        }
    for(int i=1;i<=x1;i++)
        if(!Q1[i].type)add(Q1[i].id,-1);
        else if(Q1[i].type==1)add(Q1[i].id,1);
    for(int i=1;i<=x1;i++)Q[QL+i-1]=Q1[i];
    for(int i=1;i<=x2;i++)Q[QL+x1+i-1]=Q2[i];
    binary(QL,QL+x1-1,l,mid),binary(QL+x1,QR,mid+1,r);
}
int main()
{
    IN(T);
    while(T--)
    {
        IN(n),IN(m),memset(t,0,sizeof(t)),cnt=qcnt=0;
        for(int i=1;i<=n;i++)IN(data[i]),Q[++cnt]=(query){0,0,data[i],i,0};
        for(int i=1,a,b,c;i<=m;i++)
            if(scanf("%s",opt),IN(a),IN(b),opt[0]=='C')
                Q[++cnt]=(query){0,0,data[a],a,1},Q[++cnt]=(query){0,0,b,a,0},data[a]=b;
            else IN(c),Q[++cnt]=(query){a,b,c,++qcnt,2};
        binary(1,cnt,INT_MIN,INT_MAX);
        for(int i=1;i<=qcnt;i++)printf("%d\n",ans[i]);
    }
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

1 条评论

【题解】 [Zjoi2013]K大数查询 整体二分+线段树 BZOJ – 3110 | K-XZY · 2018年1月6日 4:00 下午

[…] 有先决科技点:整体二分解决单点修改区间kth问题:传送门= ̄ω ̄= […]

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *