51Nod栈

LYK有一个栈，众所周知的是这个数据结构的特性是后进先出的。

LYK感觉这样子不太美妙，于是它决定在这个前提下将其改进，也就是说，每次插入元素时，可以在栈顶或者栈底插入，删除元素时，只能在栈顶删除。
LYK想知道每次执行完操作后当前栈中元素的最大值是多少。

第一行一个数n表示操作次数。
接下来n行，每行两个数a。若a<=1，则接下来输入一个数b。
若a=0，则在栈顶插入一个数b。
若a=1，则在栈底插入一个数b。
若a=2，则在栈顶删除一个数。

每次操作后，输出当前栈中元素的最大值是多少。
保证任意时刻栈中至少含有一个数。

由于操作数实在太多了。
于是你可以采取这种方式读入所有操作。
读入8个参数n,A,B,C,x0,a,b,MOD。 0<=A,B,C<=100000,A+B+C>0,0<=x0,a,b<=10^9,1<=MOD<=10^9,1<=n<=10000000。
有xi=(xi−1∗a+b)%MOD  。
对于第i次操作，若xi%(A+B+C)<A或者当前栈中元素<=1，则a=0，且b=xi。若A<=xi%(A+B+C)<A+B，则a=1，且b=xi，若A+B<=xi%(A+B+C)，则a=2。

输出可能很大，只需输出将所有答案的总和对1e9+7取模后的结果即可。

 

样例解释：

对应的xi：1 4 0 2 1
对应的操作：
0 1
0 4
0 0
2
1 1

 

对应的答案：

1

4

4

4

4

Input

一行8个参数，n,A,B,C,x0,a,b,MOD

Output

一行表示答案总和对1e9+7取模后的结果

Input示例

5 1 1 1 2 2 2 5

Output示例

17


模仿的这里

 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e7+5;
const int P=1e9+7;
int n,a[N],b[N];
int q[N*2],head,tail,st[N*2],first,last;
ll A,B,C,x,aa,bb,mod;
int main(){
    scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d",&n,&A,&B,&C,&x,&aa,&bb,&mod);
    for(int i=1,tot=0;i<=n;++i) {
        x=(x*aa+bb)%mod;
        ll xx=x%(A+B+C);
        if(tot<=1||xx<A) a[i]=0,b[i]=x,++tot;
        else if(A<=xx&&xx<A+B) a[i]=1,b[i]=x,++tot;
        else a[i]=2,--tot;
    }
    head=1e7+2;
    first=tail=last=head;
    int ans=0;
    for(int i=1;i<=n;++i) {
        if(!a[i]) {
            st[++last]=b[i];
            if(q[tail]<=b[i]) q[++tail]=b[i];
        }
        else if(a[i]==1) {
            st[first--]=b[i];
            while(head<tail&&q[head+1]<b[i]) ++head;
            q[head--]=b[i];
        }
        else {
            if(q[tail]==st[last]) --tail;
            --last;
        }
        ans=(ans+q[tail])%P;
    }
    printf("%d
",ans);
}