雅礼6.22考试

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^‘0‘)
#define pb push_back
#define solid const auto &
#define enter cout<<endl
#define pii pair<int,int>
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch==‘-‘)&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}
template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+‘0‘);}
template<class T>il void ot(T x){if(x<0) putchar(‘-‘),x=-x;output(x);putchar(‘\n‘);}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) cout<<a[i]<<" ";putchar(‘\n‘);}
namespace Modulo{
const int mod=998244353;
il int ad(int x,int y){return x+y>=mod?x+y-mod:x+y;}
il int sub(int x,int y){return ad(x,mod-y);}
il int mul(int x,int y){return (ll)x*y%mod;}
il void inc(int &x,int y){x=ad(x,y);}
il void inc2(int &x,int y){x=mul(x,y);}
il int qm(int x,int y=mod-2){int ret=1;while(y){if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}
template<class ...Args>il int ad(const int a,const int b,const Args &...args) {return ad(ad(a,b),args...);}
template<class ...Args>il int mul(const int a,const int b,const Args &...args) {return mul(mul(a,b),args...);}
}
// using namespace Modulo;
namespace Miracle{
const int N=3e5+5;
int n,m,d;
struct tr{
    ll sc,sum,tag;
    ll ad;
    int mul;
    void op(){
        cout<<" sc "<<sc<<" sum "<<sum<<" tag "<<tag<<" ad "<<ad<<" mul "<<mul<<endl;
    }
}t[4*N];
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
void pushup(int x){
    t[x].sc=t[ls].sc+t[rs].sc;
    t[x].sum=t[ls].sum+t[rs].sum;
}
void tag(int x,int l,int r,ll ad,ll mul,ll tag){
    t[x].sum+=t[x].sc*mul+(ll)(r-l+1)*tag;
    t[x].sc+=(ll)(r-l+1)*ad;

    t[x].tag+=tag+(ll)mul*t[x].ad;
    
    t[x].ad+=ad;
    t[x].mul+=mul;
    
}
void pushdown(int x,int l,int r){
    tag(ls,l,mid,t[x].ad,t[x].mul,t[x].tag);
    tag(rs,mid+1,r,t[x].ad,t[x].mul,t[x].tag);
    t[x].mul=0;
    t[x].ad=0;
    t[x].tag=0;
}
void add(int x,int l,int r,int L,int R,int c){
//    cout<<" add "<<l<<" "<<r<<" || "<<L<<" "<<R<<" c "<<c<<endl;
    if(L<=l&&r<=R){
        t[x].sc+=(ll)(r-l+1)*c;
        t[x].ad+=c;
        return;
    }
    pushdown(x,l,r);
    if(L<=mid) add(ls,l,mid,L,R,c);
    if(mid<R) add(rs,mid+1,r,L,R,c);
    pushup(x);
}
void mul(int x,int l,int r,int L,int R){
//    cout<<" mul "<<l<<" "<<r<<" || "<<L<<" "<<R<<endl;
    if(L<=l&&r<=R){
        t[x].sum+=t[x].sc;
        t[x].tag+=t[x].ad;
        t[x].mul++;
        return;
    }
    pushdown(x,l,r);
    if(L<=mid) mul(ls,l,mid,L,R);
    if(mid<R) mul(rs,mid+1,r,L,R);
    pushup(x);
}
ll query(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return t[x].sum;
    }
    pushdown(x,l,r);
    ll ret=0;
    if(L<=mid) ret+=query(ls,l,mid,L,R);
    if(mid<R) ret+=query(rs,mid+1,r,L,R);
    return ret;
}
struct qs{
    int id,l,r;
    bool friend operator <(qs a,qs b){
        return a.r<b.r;
    }
}q[N];
ll ans[N];
int a[N],b[N],c[N];
set<int>s;

struct po{
    int p,v;
    po(){}
    po(int pp,int vv){
        p=pp;v=vv;
    }
};
struct STA{
    po sta[N];
    int tp;
    po top(){
        return sta[tp];
    }
    void pop(){
        --tp;
    }
    void ins(int p,int v){
        sta[++tp]=po(p,v);
    }
}sb,sm;
int L;
int main(){
    rd(n);rd(d);rd(m);
    for(reg i=1;i<=n;++i){
        rd(a[i]);b[i]=a[i]%d;
        c[i]=a[i]/d;
    }
    for(reg i=1;i<=m;++i){
        rd(q[i].l);rd(q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+m+1);
    
    add(1,1,n,1,n,1);
    
    sb.sta[0]=po(0,0);
    sm.sta[0]=po(0,0);
    
    
//    prt(b,1,n);
//    prt(c,1,n);
    
    L=1;
    
    int ptr=1;
    for(reg i=1;i<=n;++i){
//        cout<<" ii ---------------"<<i<<endl;
        add(1,1,n,1,i,-1);
        
        while(L<i&&s.find(a[i])!=s.end()){
            s.erase(a[L]);++L;
        }
        while(L<i&&b[L]!=b[i]){
            s.erase(a[L]);++L;
        }
        s.insert(a[i]);
//        cout<<"now L "<<L<<" sz "<<s.size()<<endl;
        
        while(sb.tp&&sb.top().v<=c[i]){
            po now=sb.top();
            sb.pop();
            add(1,1,n,sb.top().p+1,now.p,-now.v);    
        }
        add(1,1,n,sb.top().p+1,i,c[i]);
        sb.ins(i,c[i]);
        
        while(sm.tp&&sm.top().v>=c[i]){
            po now=sm.top();
            sm.pop();
            add(1,1,n,sm.top().p+1,now.p,now.v);
        }
        add(1,1,n,sm.top().p+1,i,-c[i]);
        sm.ins(i,c[i]);
        

//        dfs(1,1,n);
        
        mul(1,1,n,L,i);
        //    if(i!=4)
//        dfs(1,1,n);
        
        
        while(ptr<=m&&q[ptr].r==i){
            ans[q[ptr].id]=query(1,1,n,q[ptr].l,q[ptr].r);
            ++ptr;
        }
//        cout<<" ans "<<ans[1]<<endl;
        
//        dfs(1,1,n);
        
    }
    for(reg i=1;i<=m;++i){
        ot(ans[i]);    
    }
    return 0;
}

}
signed main(){
//    freopen("arithmetic.in","r",stdin);
//    freopen("arithmetic.out","w",stdout);
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
*/