题面

三个操作

1.在当前数列最左端加入\(k\)个初始为\(0\)的数

2.在当前数列最右端加入\(k\)个初始为\(0\)的数

3.将当前数列从左到右第\(i\)个数加上\(b+(i-1)k(b>0,k>0)\)

请在每一次操作之后输出当前数列的最小值以及最小值所在的位置，如果有多个相同的最小值取最左端的

题解

首先有两个结论

1.如果在左端加入一个数，那么它后面的所有数都没有用了

证明：因为每一次\(3\)操作后面加的永远比前面的多，而且值相同时要取最左边的，所以左边加入一个之后后面的都没用了

2.不管是左端还是右端，加入的\(k\)个数里只有最左端的是有用的

证明同\(1\)

那么简单来说过程就是这样，我们需要一个能够不断往后添加元素的东西，每一次如果前面加了值我们就把它暴力重构

易发现我们需要维护的是一个递减的序列（因为如果有一个元素大于前面的那么前面那个并没有什么卵用），而且有可能加着加着某一个数突然大于前面了，得把它删去

那么很明显就是一个链表了，只有这玩意儿资瓷快速在数列中间删数

于是我们接下来的过程都假定左端点固定（因为左端点一变我们就需要直接重构）

设当前左端点为\(1\)，那么后面加入的每个数的位置都是已经定的，对于加的值我们可以维护\(\sum b\)和\(\sum s\)，那么到时候需要用的时候可以一起加上去。对于一个新加入的值，设当前\(tmpb=\sum b,tmps=\sum s\)，我们需要把它的值减去\(tmpb+(id-1)tmps\)（其中\(id\)为它的位置），这样才能保证后面加上懒标记的时候它的值是真的

会改变序列中数的大小关系的只与\(s\)有关，对于数列中相邻的两个数，如果它们的位置之差为\(k\)，那么一次\(3\)操作的\(s\)会使它们之间的值的差减少\(ks\)，设它们原来的差为\(val\)，那么只要之后的\(s\)操作的总和达到了\(val/k\)（这里是上取整），那么后面那个数就废了，我们就可以删了它

我们每次插入一个数的时候算出它和前面那个数此时相差的值，并记录一下需要达到的\(s\)，并把它放进一个优先队列里。每一次\(3\)操作的时候都不断取出最顶端的元素看看是否需要删

注意，我们算出的\(s\)是之后还需要多少，但是\(tmps\)记录的是从开始到现在有多少，所以放进队列的时候还需要加上当前的\(tmps\)

还有，每一次删数的时候，设当前删的数为\(p\)，那么队列里记录的\(p\)右边那个数和\(p\)的差就没有意义了，要删掉，所以我们需要的是一个可删堆

然后没有然后了

ps：为了好看一点第一次用了指针……结果\(bug\)死活调不出来……以后再也不乱搞了……

//minamoto#include
    
     #define R register#define ll long long#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R ll x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]='\n';}const int N=5e5+5;struct node{    node *lc,*rc;int s,id;ll v,c;    inline void init(R int ss,R int Id,R ll vv){s=ss,id=Id,v=vv,lc=rc=NULL;}}pool[N],*p[N],*T,*g;struct point{    node *c;ll v;    point(){c=NULL,v=0;}    point(node *cc,ll vv):c(cc),v(vv){}    inline bool operator <(const point &b)const{return v>b.v;}    inline bool operator ==(const point &b)const{return c==b.c&&v==b.v;}};struct Queue{    priority_queue
      
       A,B;    inline void push(R point x){A.push(x);}    inline void pop(R point x){B.push(x);}    inline void pop(){A.pop();}    inline bool empty(){        while(!B.empty()&&A.top()==B.top())A.pop(),B.pop();        return A.empty();    }    inline point top(){        while(!B.empty()&&A.top()==B.top())A.pop(),B.pop();        return A.top();    }}q;int n,m,tot,op,b,s,k,sum;ll sumb,sums,tmpb,tmps;inline void insh(){p[++tot]->init(sum+k,1,0),T=p[tot],tmpb=tmps=0;while(!q.empty())q.pop();}inline ll val(node *it){return tmpb+tmps*(it->id-1)+it->v;}void inst(){    if(val(T)==0)return T->s+=k,void();    p[++tot]->init(k,sum+1,-tmpb-tmps*sum);    p[tot]->c=(val(T)-val(p[tot])+T->s-1)/T->s+tmps;    p[tot]->lc=T,T->rc=p[tot],q.push(point(p[tot],p[tot]->c));    T=p[tot];}void update(){    tmpb+=b,tmps+=s;    while(!q.empty()&&q.top().v<=tmps){        g=q.top().c,q.pop();        if(g==T)T=g->lc,T->s+=g->s,T->rc=NULL;        else{            g->lc->rc=g->rc,g->rc->lc=g->lc,g->lc->s+=g->s;            q.pop(point(g->rc,g->rc->c));            g->rc->c=(val(g->lc)-val(g->rc)+g->lc->s-1)/g->lc->s+tmps;            q.push(point(g->rc,g->rc->c));        }    }}int main(){//  freopen("testdata.in","r",stdin);    n=read(),m=read();    fp(i,1,N-5)p[i]=&pool[i];    k=n,insh(),sum=k;    while(m--){        op=read();        switch(op){            case 1:k=read(),insh(),sum+=k;break;            case 2:k=read(),inst(),sum+=k;break;            case 3:b=read(),s=read(),update();break;        }        print(T->id),sr[C]=' ',print(val(T));    }    return Ot(),0;}