Luogu P3722 [AH2017/HNOI2017]影魔

题面

这题一开始想用莫队，然后对每个点快速算与它有关的点对的贡献，结果算不出来。。。

然后看题解发现自己把K_i互不相同这个至关重要的条件给漏掉了。。。（虽然知道也做不出

看了题解发现真的很妙啊～

首先把询问离线下来，然后就可以预处理所有点对的贡献，然后对每个询问累加即可。

因为一对点的贡献与这两点间的最大值有关，所以可以直接枚举这个最大值，对所有以这个值为最大值的点对做贡献。

先对每个点预处理出L[i]与R[i]表示i左边第一个大于k[i]的数的位置，和右边的位置。

对于每个点i，可以确定：

点对(L[i],R[i])的攻击力为p1；
对于l∈[L[i]+1,i-1]，点对(l,R[i])的攻击力为p2；
对于r∈[i+1,R[i]-1]，点对(L[i],r)的攻击力为p2；
其他点对攻击力均为0；

确定每个点对的攻击力后，每个询问相当于一个二维数点，可以把其中一维转化为时间，动态加点（即扫到一个位置时将第一维是这个位置的点全部加入，然后差分求扫这个区间时在这个区间中加的数的总和），另一维直接用线段树维护区间加区间求和。

代码：

  1 // luogu-judger-enable-o2
  2 #include<bits/stdc++.h>
  3 using namespace std;
  4 #define ll long long
  5 #define N 200007
  6 const int inf=0x3f3f3f3f;
  7 struct str1
  8 {
  9     int l,r;
 10     ll d;
 11 };
 12 struct str2
 13 {
 14     ll op;
 15     int l,r,id;
 16 };
 17 int n,m,a[N],L[N],R[N];
 18 ll p1,p2,ans[N];
 19 vector<str1> my[N];
 20 vector<str2> qy[N];
 21 stack<int> q;
 22 ll sum[N<<2],add[N<<2];
 23 void mark(int k,int l,int r,ll d)
 24 {
 25     sum[k]+=(r-l+1)*d;
 26     add[k]+=d;
 27 }
 28 void pushdown(int k,int l,int r,int mid)
 29 {
 30     mark(k<<1,l,mid,add[k]);
 31     mark(k<<1|1,mid+1,r,add[k]);
 32     add[k]=0;
 33 }
 34 void modify(int k,int l,int r,int x,int y,ll d)
 35 {
 36     if(l>=x&&r<=y)return mark(k,l,r,d);
 37     int mid=l+r>>1,lc=k<<1,rc=k<<1|1;
 38     pushdown(k,l,r,mid);
 39     if(x<=mid)modify(lc,l,mid,x,y,d);
 40     if(y>mid)modify(rc,mid+1,r,x,y,d);
 41     sum[k]=sum[lc]+sum[rc];
 42 }
 43 ll query(int k,int l,int r,int x,int y)
 44 {
 45     if(l>=x&&r<=y)return sum[k];
 46     int mid=l+r>>1,lc=k<<1,rc=k<<1|1;
 47     ll ans=0;
 48     pushdown(k,l,r,mid);
 49     if(x<=mid)ans+=query(lc,l,mid,x,y);
 50     if(y>mid)ans+=query(rc,mid+1,r,x,y);
 51     return ans;
 52 }
 53 void mdy(int l,int r,ll d)
 54 {
 55     modify(1,1,n,l,r,d);
 56 }
 57 ll qry(int l,int r)
 58 {
 59     return query(1,1,n,l,r);
 60 }
 61 int read()
 62 {
 63     int x;
 64     char c;
 65     while((c=getchar())<48||c>57);
 66     x=c-48;
 67     while((c=getchar())>=48&&c<=57)
 68         x=x*10+c-48;
 69     return x;
 70 }
 71 int main()
 72 {
 73     int i,j,x,y;
 74     //freopen("data.in","r",stdin);
 75     n=read(),m=read(),p1=read(),p2=read();
 76     for(i=1;i<=n;i++)
 77         a[i]=read();
 78     a[0]=inf,a[n+1]=inf;
 79     q.push(0);
 80     for(i=1;i<=n+1;i++)
 81     {
 82         while(a[q.top()]<a[i])
 83             R[q.top()]=i,q.pop();
 84         L[i]=q.top();
 85         q.push(i);
 86     }
 87     for(i=1;i<=n;i++)
 88     {
 89         int l=L[i],r=R[i];
 90         if(l!=0&&r!=n+1)my[r].push_back({l,l,p1});
 91         if(l!=0&&r>i+1)my[l].push_back({i+1,r-1,p2});
 92         if(r!=n+1&&l<i-1)my[r].push_back({l+1,i-1,p2});
 93     }
 94     for(i=1;i<=m;i++)
 95     {
 96         x=read(),y=read();
 97         qy[x-1].push_back({-1,x,y,i});
 98         qy[y].push_back({1,x,y,i});
 99         ans[i]+=(y-x)*p1;
100     }
101     for(i=0;i<=n;i++)
102     {
103         int s=my[i].size();
104         for(j=0;j<s;j++)
105         {
106             str1 u=my[i][j];
107             mdy(u.l,u.r,u.d);
108         }
109         s=qy[i].size();
110         for(j=0;j<s;j++)
111         {
112             str2 u=qy[i][j];
113             ans[u.id]+=u.op*qry(u.l,u.r);
114         }
115     }
116     for(i=1;i<=m;i++)
117         printf("%lld
",ans[i]);
118     return 0;
119 }