HNOI2017 影魔

题面

我们先不考虑p1,考虑一个点对如果有任意一个点的权值大于之间的所有点权,那么就有p2的贡献。

那么p1会算为2个p2.

怎么枚举呢?

先考虑单侧,另一侧反过来即可。

用单调栈记录每个点x后面第一个比它大的z。

那么x<yzx<y\le z的所有y都满足(x,y)有p2的贡献(显然)

然后这样就完了你成功的获得了30分也就是p1=2p2的部分。

由于点权组成了排列,不存在有2个点点权相等。

那么对于p1的贡献,显然只可能一边是最大值一边是次大值。

那么我们在上面找到z的时候,显然(x,z)(x,z)点对的贡献应该是p1,但是会被算为2p2,那么直接加上p12p2p1-2p2的贡献即可。

具体怎么算呢?

先把询问按照左端点排序。

枚举x从n到1,然后找到z,对于每个点对(x,y)的贡献,直接加在y上。然后对于所有左端点为x的询问,直接求l到r的贡献和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/*
Author: CNYALI_LK
LANG: C++
PROG: 3722.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
ll cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;}
do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
putchar(end);
}
struct _ask{
ll t,l,r;
_ask(){}
_ask(ll _t){
t=_t;
l=read();r=read();
}
};
_ask ask[204847];

ll n,m,p1,p2;
ll a[204847];
struct smt{
smt *l,*r;
ll _l,_r,sum,add;
#define push_up sum=l->sum+r->sum
smt(ll ls,ll rs){
_l=ls;_r=rs;
sum=add=0;
if(ls!=rs){
ll mid=(ls+rs)>>1;
l=new smt(ls,mid);
r=new smt(mid+1,rs);
}
}
void put_tag(ll w){
sum+=w*(_r-_l+1);
add+=w;
}
void push_down(){
l->put_tag(add);
r->put_tag(add);
add=0;
}
void change(ll ls,ll rs,ll w){
if(ls<=_l&&_r<=rs)put_tag(w);
else{
push_down();
if(ls<=l->_r)l->change(ls,rs,w);
if(rs>=r->_l)r->change(ls,rs,w);
push_up;
}
}
ll query(ll ls,ll rs){
if(ls<=_l&&_r<=rs)return sum;
else{
push_down();
ll ans=0;
if(ls<=l->_r)ans+=l->query(ls,rs);
if(rs>=r->_l)ans+=r->query(ls,rs);
return ans;
}
}
};
ll nx[204847],ans[204847];
void calc(){
sort(ask+1,ask+m+1,[](_ask a,_ask b){return a.l<b.l;});
stack<ll> stk;
stk.push(n+1);
smt *r=new smt(1,n+1);
ll j=m;
for(ll i=n;i;--i){
while(a[stk.top()]<a[i])stk.pop();
nx[i]=stk.top();
stk.push(i);
r->change(i+1,nx[i],p2);
r->change(nx[i],nx[i],p1-2*p2);
while(ask[j].l==i){
ans[ask[j].t]+=r->query(ask[j].l,ask[j].r);
--j;
}
}
}
int main(){
#ifdef cnyali_lk
freopen("3722.in","r",stdin);
freopen("3722.out","w",stdout);
#endif
n=read();
m=read();p1=read();p2=read();
for(ll i=1;i<=n;++i)a[i]=read();
a[n+1]=n+1;
for(ll i=1;i<=m;++i){
ask[i]=_ask(i);
}
calc();
reverse(a+1,a+n+1);
for(ll i=1;i<=m;++i){ask[i].l=n+1-ask[i].l;ask[i].r=n+1-ask[i].r;swap(ask[i].l,ask[i].r);}
calc();
for(ll i=1;i<=m;++i)write(ans[i],'\n');
return 0;
}
文章目录
|

博客使用Disqus作为评论系统