玩(lay)

题目名称

你的昆特牌打的太好啦！不一会你就 \(\tt{AK}\) 了 \(\tt{NOGP}\)，只能无聊地堆牌玩！

题目描述

你有一些矩形卡牌，每次你会作如下三个操作：

紧挨着最后一张牌往牌后面放一张牌，这张牌的底边与 \(X\) 轴重合且位于第一象限。（第一张牌最左边位于 \(X=0\) 处）
拿走一张牌，并把后面的牌向前推到与前一张牌右边重合。
询问\([l , r]\)（坐标）这一段牌最高的高度。

对于边界情况，在两张牌交界处视为最高的那张牌的高度。

输入输出可能需要加速！

输入输出格式

输入格式

第一行两个数 \(N\)、 \(C\) 表示操作数、离线操作还是在线；

接下来 \(N\) 行每行是如下三种之一

\(T=1\)，接下来 \(LEN\)、 \(H\) 分别表示插入的牌的长、高；

\(T=2\)，接下来 \(X\) 表示拿走哪一张牌，牌的编号按出现顺序由小到大，从 \(1\) 开始（不是操作序号！），删除的牌不会改变序号，若序号表示的牌已被删除则不操作；

\(T=3\)，接下来 \(L\)、 \(R\) 表示询问区间；若询问区间上没牌，输出 \(0\)。

若 \(C=1\),则上面输入中的 \(LEN\)、 \(H\)（仅这两项！）需要以下式子算出（\(lastans\) 为最近一次询问答案，初值为 \(0\)）

真实输入\(=(\)输入\(\times 2333 + lastans\times 666 )\pmod{10^8+7}+1\)。

输出格式

对每一个询问操作输出该段最高的位置高度是多少。

说明

对于\(40\%\)的数据，没有删除操作；

对于额外\(20\%\)的数据， \(C=0\)；

对于\(80\%\)的数据， \(N\le 2 \times 10^5\)；

对于\(100\%\)的数据， \(N \le 5\times 10^5\) ， \(LEN,H\le 10^9\)， \(L\)、 \(R\) 不会超过 \(10^{18}\) 范围，输入的没有负数

并不难。

上午打了一个\(fhq\)平衡树维护，因为写了三个\(\tt{split}\)再加上第一题模拟写挂写的很烦，然后就挂了。

下午换了思路写了写线段树。

主题思路是对进入的牌的顺序建线段树，维护区间长度加和区间高度最大值

每次询问的时候现在线段树上二分一下找到询问的区间，然后再进去询问就可以了。

（结果还是写了三个\(\tt{query}\)，事实上一个应该就可以了

删除插入都比较简单了。

Code:

#include <cstdio>

#define ll long long

const int N=5e5+10;

ll sum[N<<2],mx[N<<2];

#define ls id<<1

#define rs id<<1|1

ll Max(ll x,ll y){return x>y?x:y;}

void updata(int id)

{

    sum[id]=sum[ls]+sum[rs];

    mx[id]=Max(mx[ls],mx[rs]);

}

void change(int id,int l,int r,int p,ll d,ll h)

{

    if(l==r)

    {

        sum[id]=d,mx[id]=h;

        return;

    }

    int mid=l+r>>1;

    if(p<=mid) change(ls,l,mid,p,d,h);

    else change(rs,mid+1,r,p,d,h);

    updata(id);

}

int queryL(int id,int l,int r,ll p)

{

    if(l==r) return l;

    int mid=l+r>>1;

    if(sum[ls]<p) return queryL(rs,mid+1,r,p-sum[ls]);

    else return queryL(ls,l,mid,p);

}

int queryR(int id,int l,int r,ll p)

{

    if(l==r) return l;

    int mid=l+r>>1;

    if(sum[ls]<=p) return queryR(rs,mid+1,r,p-sum[ls]);

    else return queryR(ls,l,mid,p);

}

int query(int id,int L,int R,int l,int r)

{

    if(l==L&&r==R) return mx[id];

    int Mid=L+R>>1;

    if(r<=Mid) return query(ls,L,Mid,l,r);

    else if(l>Mid) return query(rs,Mid+1,R,l,r);

    else return Max(query(ls,L,Mid,l,Mid),query(rs,Mid+1,R,Mid+1,r));

}

int main()

{

    int c,op,n,In=0;

    scanf("%d%d",&n,&c);

    ll lastans=0,LEN,H,l,r;int id;

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&op);

        if(op==1)

        {

            scanf("%lld%lld",&LEN,&H);

            if(c==1)

            {

                LEN=(LEN*2333+lastans*666)%100000007+1;

                H=(H*2333+lastans*666)%100000007+1;

            }

            change(1,1,n,++In,LEN,H);

        }

        else if(op==3)

        {

            scanf("%lld%lld",&l,&r);

            printf("%lld\n",lastans=query(1,1,n,queryL(1,1,n,l),queryR(1,1,n,r)));

        }

        else

        {

            scanf("%d",&id);

            change(1,1,n,id,0,0);

        }

    }

    return 0;

}

2018.11.6

巴特西

玩(lay) 解题报告