daima test

发布于 2018-08-30  282 次阅读


123132
132
123

132
132
132
132
132
132
132
132
1321
231
321234156
465
41651
65165
165123132
132
123
132
132
132
132
132
132
132
132
1321
231
321234156
465
41651
65165
165123132
132
123
132
132
132
132
132
132
132
132
1321
231
321234156
465
41651
65165
165123132
132
123
132
132
132
132
132
132
132
132
1321
231
321234156
465
41651
65165
165123132
132
123
132
132
132
132
132
132
132
132
1321
231
321234156
465
41651
65165
165123132
132
123
132
132
132
132
132
132
132
132
1321
231
321234156
465
41651
65165
165123132
132
123
132
132
132
132
132
132
132
132
1321
231
321234156
465
41651
65165
165
465
1
65165
1

#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200010;

typedef long long ll;
int n,m,p1,p2;
int tot1,tot2;
int k[N],L[N],R[N];

ll ans[N],bbb[N],ccc[N];

vector<int> xx[N],yy[N];
vector<int> mx[N],my[N];

struct pack
{
    int f,s;
    pack(){}
    pack(int a,int b):f(a),s(b){}
}st[N],t;
struct line
{
    int a,b1,b2,c;
}X[N<<1],Y[N];
struct question
{
    int l,r,id;
}ques[N];

inline void fuck() 
{ 
    int tp=1;
    st[tp]=pack(k[1],1);
    for(int i=2;i<=n;++i) 
    {
        t=pack(k[i],i);
        while(tp&&st[tp].f<t.f) --tp;
        if(!tp) L[i]=0;
        else L[i]=st[tp].s;
        st[++tp]=t; 
    } 

    R[n]=n+1;
    st[tp=1]=pack(k[n],n);
    for(int i=n-1;i>=1;--i) 
    {
        t=pack(k[i],i);
        while(tp&&st[tp].f<t.f) --tp;
        if(!tp) R[i]=n+1;
        else R[i]=st[tp].s;
        st[++tp]=t;
    }
}
inline void add(int x,int y) 
{
    for(int i=x;i<=n;i+=i&-i) bbb[i]+=y,ccc[i]+=x*y;
} 
inline ll qqq(int x) 
{
    long long sum=0;
    for(int i=x;i;i-=i&-i) sum+=(x+1)*bbb[i]-ccc[i];
    return sum;
}
inline void clean()
{
    memset(bbb,0,sizeof bbb);
    memset(ccc,0,sizeof ccc);
}
inline void fuckagain() {
    int poi;
    line x; question y;
    for(int i=n;i>=1;--i) 
    {
        for(int j=0;j<mx[i].size();++j) 
        {
      //  printf("%d\n",mx[i].size());
            poi=mx[i][j]; x=X[poi];
           // printf("x.b1=%d x.b2=%d x.c=%d\n",x.b1,x.b2,x.c);
            add(x.b1,x.c),add(x.b2+1,-x.c);//add(1,1,n,LX[g]);
        }
        for(int j=0;j<xx[i].size();++j) 
        { 
            poi=xx[i][j]; y=ques[poi];
           // printf("qx[%d][%d]=%d\n",i,j,xx[i][j]);
          // printf("i=%d j=%d g=%d r=%d l=%d\n",i,j,g,y.r,y.l); 
            ans[poi]+=qqq(y.r)-qqq(y.l-1);
        }
    }
    clean();
    for(int i=1;i<=n;++i) 
    {
        for(int j=0;j<my[i].size();++j) 
        {
            poi=my[i][j]; x=Y[poi];
            add(x.b1,x.c),add(x.b2+1,-x.c);
        }
        for(int j=0;j<yy[i].size();++j) 
        {
            poi=yy[i][j]; y=ques[poi]; 
            ans[poi]+=qqq(y.r)-qqq(y.l-1);
        }
    }
}
int main() 
{
    scanf("%d%d%d%d",&n,&m,&p1,&p2);
    for(int i=1;i<=n;++i) scanf("%d",&k[i]);
    fuck();
    //for(int i=1;i<=n;++i) printf("L[%d]=%d R[%d]=%d\n",i,L[i],i,R[i]);
    for(int i=1;i<=m;++i) 
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ques[i].l=x,ques[i].r=y,ques[i].id=i;
        xx[x].push_back(i),yy[y].push_back(i);
    }
   /* for(int i=1;i<=m;++i)
    {
        for(int j=0;j<xx[i].size();++j) printf("xx[%d][%d]=%d\n",i,j,xx[i][j]);
    }*/
    for(int i=1;i<=n;++i) 
    {
        if(L[i]!=0&&R[i]!=n+1) 
        {
            X[++tot1].c=p1;
            X[tot1].b1=X[tot1].b2=R[i];
          //  printf("X[%d].a=%d val=%d b1=b2=%d\n",t1,LX[t1].a,LX[t1].c,LX[t1].b1);
            mx[L[i]].push_back(tot1);
        }
        if(L[i]!=0||R[i]!=n+1) 
        {
            if(i+1<=R[i]-1) 
            {
                X[++tot1].b1=i+1,X[tot1].b2=R[i]-1;
                X[tot1].c=p2, mx[L[i]].push_back(tot1);
            }
            if(L[i]+1<=i-1) 
            {
                Y[++tot2].b1=L[i]+1,Y[tot2].b2=i-1;
                Y[tot2].c=p2, my[R[i]].push_back(tot2);
            }
        }
    }
    fuckagain();
    for(int i=1;i<=m;++i) printf("%lld\n",ans[i]+(ques[i].r-ques[i].l)*p1);
    return 0;
}
0.00 avg. rating (0% score) - 0 votes

一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。