首先这题现在在BZOJ上是没数据的，你可以选择python2B获得AC，也可以去洛谷上交。
选择第一个选项的现在可以不用看了......
关于这题的题意，击破的一次攻击即使溢出也不双倍，否则你过不了样例。
然后考虑每个防御只会被击破一次，那么我们可以像HEOI2017相逢是问候那样用一个线段树去维护是否被击破。
然而那个题每次暴力push到底就行了，但这个题如果这样做，会发现在push时可能没有任何防御被击破，复杂度不对......
考虑用奇怪的办法保证存在防御被击破，我们维护区间的min，如果这个区间的min<=当前攻击值，则我们有必要在这个区间push到底。
然后就是实现的问题，自己YY一下就好了，我是用一个单独的函数去实现的push到底这个操作......
注意各种分类讨论......
别问我为什么刷这种水题......
今天好不容易不考试写神题也写不动啊......
我的代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define debug cout
typedef long long int lli;
using namespace std;
const int maxn=1e5+1e2;
const int mod=1e9+;
const int inf=0x3f3f3f3f; int in[maxn<<];
int l[maxn<<],r[maxn<<],lson[maxn<<],rson[maxn<<],siz[maxn<<],full[maxn<<],cnt; // size means number needs to be doubled .
lli sum[maxn<<],miv[maxn<<],lazy[maxn<<]; // lazy means attack not pushsed ( not doubled ) . inline void build(int pos,int ll,int rr) {
l[pos] = ll , r[pos] = rr , full[pos] = rr - ll + ;
if( ll == rr ) {
miv[pos] = in[ll];
return;
} const int mid = ( ll + rr ) >> ;
build(lson[pos]=++cnt,ll,mid) , build(rson[pos]=++cnt,mid+,rr);
miv[pos] = min( miv[lson[pos]] , miv[rson[pos]] );
}
inline void apply(int pos,lli x) {
lazy[pos] += x , sum[pos] += ( full[pos] + siz[pos] ) * x;
if( miv[pos] != inf ) miv[pos] -= x;
}
inline void push(int pos) {
if( !lazy[pos] ) return;
apply(lson[pos],lazy[pos]) , apply(rson[pos],lazy[pos]) , lazy[pos] = ;
}
inline void maintain(int pos) {
siz[pos] = siz[lson[pos]] + siz[rson[pos]] ,
sum[pos] = sum[lson[pos]] + sum[rson[pos]] ,
miv[pos] = min( miv[lson[pos]] , miv[rson[pos]] );
}
inline void chain(int pos,lli x) {
if( x < miv[pos] ) { // nothing will be destoryed .
apply(pos,x);
return;
}
if( l[pos] == r[pos] ) { // assert x <= miv[pos] .
sum[pos] += x , siz[pos] = , miv[pos] = inf;
} else { // push lazy at the same time .
chain(lson[pos],x+lazy[pos]) , chain(rson[pos],x+lazy[pos]) , lazy[pos] = ;
maintain(pos);
}
}
inline void update(int pos,int ll,int rr,lli x) {
if( r[pos] < ll || rr < l[pos] ) return;
if( ll <= l[pos] && r[pos] <= rr ) return chain(pos,x);
push(pos);
update(lson[pos],ll,rr,x) , update(rson[pos],ll,rr,x);
maintain(pos);
}
inline lli query(int pos,int ll,int rr) {
if( r[pos] < ll || rr < l[pos] ) return ;
if( ll <= l[pos] && r[pos] <= rr ) return sum[pos];
push(pos);
return query(lson[pos],ll,rr) + query(rson[pos],ll,rr);
} int main() {
static int n,m;
static char o[];
static lli ans;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",in+i);
build(cnt=,,n);
for(int i=,l,r,x;i<=m;i++) {
scanf("%s%d",o,&l);
if( *o == 'A' ) {
scanf("%d%d",&r,&x);
update(,l,r,x);
} else if( *o == 'Q' ) {
( ans += query(,l,l) % mod ) %= mod;
}
}
printf("%lld\n",ans);
return ;
}
最后给大家送上数据和对拍器，用lemon的格式打包的。
链接: https://pan.baidu.com/s/1n518YAQFYH02hi2ZNB41EQ 密码: ahym