1. 题目

传送门= ̄ω ̄=

2. 题解

mmp好久没碰到这么恶心的题目惹!

因为不会整体二分&CDQ分治,所以就写惹树套树。

怎么说呢=。=

  • 此题树套树卡常
  • 还卡空间,线段树需要动态开点
  • 理论上要开long long但开了就TLE=。=

所以,,,最好的解决方法是用zkw线段树常数小

但我不会啊!

而且也不知道zkw会不会被卡

但是我们通过查阅hzw的题解&luogu讨论可知:此题可以直接忽略插入负数的操作!

于是就能开unsigned int用普通线段树轻松AC了。。。

具体做法的话基本和主席树的思路是一样的:

外层是一颗权值线段树,每个节点维护该节点对应的颜色区间内的所有颜色在题目中的数轴上某个区间内的出现次数总和。

也就是每个外层的线段树节点对应了一颗大小为$n$的线段树,这颗线段树维护的是每个数轴上的区间内该外层节点对应的颜色的出现次数。

然后我们查询一个区间内排序第$k$的数值(颜色)的话就在外层线段树上二分。

一开始外层线段树的根节点对应颜色区间$[-n,n]$,那么根节点的左儿子对应的内层线段树查询区间$[l,r]$的和就能得到在区间$[l,r]$内比$\frac{-n+n}{2}$小的值有多少个,从而得到$\frac{-n+n}{2}$的排名,最后运用类似二分答案的思想,判断该排名是小了还是大了,小了说明答案在根的右儿子里,否则在左儿子里。

最后输出答案即可。

代码:

#include <bits/stdc++.h>
#define LS(a) (a<<1)
#define RS(a) (a<<1|1)
using namespace std;
typedef unsigned int UL;
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 N{UL s[2],d,tag;}e[20000005];
UL n,m,cnt,A,B,C;
int D;
void pdown(UL a,UL L,UL R)
{
    if(!e[a].s[0])e[a].s[0]=++cnt;
    if(!e[a].s[1])e[a].s[1]=++cnt;
    if(e[a].tag)
    {
        UL l=e[a].s[0],r=e[a].s[1],mid=(L+R)>>1;
        e[l].d+=(mid-L+1)*e[a].tag,e[l].tag+=e[a].tag;
        e[r].d+=(R-mid)*e[a].tag,e[r].tag+=e[a].tag;
        e[a].tag=0;
    }
}
void pup(UL a){e[a].d=e[e[a].s[0]].d+e[e[a].s[1]].d;}
struct segment_tree
{
    UL root;
    void update(UL l,UL r,UL d,UL&a,UL L,UL R)
    {
        if(!a)a=++cnt;
        if(l<=L&&R<=r){e[a].d+=(R-L+1)*d,e[a].tag+=d;return;}
        pdown(a,L,R);
        UL mid=(L+R)>>1;
        if(l<=mid)update(l,r,d,e[a].s[0],L,mid);
        if(r>mid)update(l,r,d,e[a].s[1],mid+1,R);
        pup(a);
    }
    UL query(UL l,UL r,UL a,UL L,UL R)
    {
        if(!a)return 0;
        if(l<=L&&R<=r)return e[a].d;
        pdown(a,L,R);
        UL tot=0,mid=(L+R)>>1;
        if(l<=mid)tot+=query(l,r,e[a].s[0],L,mid);
        if(r>mid)tot+=query(l,r,e[a].s[1],mid+1,R);
        return tot;
    }
}t[20000005];
void work_update()
{
    if(D<0)return;
    D=n-D;
    UL a=1,L=0,R=n,mid;
    while(a)
    {
        t[a].update(B,C,1,t[a].root,1,n),mid=(L+R)>>1;
        if(L==R)break;
        if(D<=mid)a=LS(a),R=mid;
        else a=RS(a),L=mid+1;
    }
}
void work_query()
{
    UL a=1,tmp,L=0,R=n,mid;
    while(L<R)
    {
        mid=(L+R)>>1,tmp=t[LS(a)].query(B,C,t[LS(a)].root,1,n);
        if(tmp>=D)a=LS(a),R=mid;else a=RS(a),L=mid+1,D-=tmp;
    }
    printf("%d\n",n-L);
}
int main()
{
    IN(n),IN(m);
    while(m--)
    {
        IN(A),IN(B),IN(C),IN(D);
        if(A==1)work_update();
        else work_query();
    }
    return 0;
}
分类: 文章

XZYQvQ

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

发表评论

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

你是机器人吗? =。= *