题目大意:
定义只含数字$4,7$的数字为幸运数, 给定序列, 区间加正数, 区间询问多少个幸运数
题解:
对于每一个数, 求出它和第一个比它大的幸运数之差, 则问题转化为区间加,查询$0$的个数
可以维护最大值即最大值的个数, 对于最大值$<=0$直接打标记修改即可
对于最大值$>0$的暴力转移到下一个幸运数,
因为对于每个幸运数来说, 最多有n个元素暴力修改, 可以看成n个点单点更新
所以暴力修改的复杂度$O(Cnlogn)$, $C$为总幸运数个数
总复杂度$O((n+m)logn+Cnlogn)$
#include <iostream>
#include <algorithm>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define mid ((l+r)>>1)
#define lc (o<<1)
#define rc (lc|1)
#define ls lc,l,mid
#define rs rc,mid+1,r
using namespace std; const int N = 4e5+, INF = 0x3f3f3f3f;
int n, m, ql, qr;
int a[N], s[N]; struct _ {
int mx, cnt, tag;
_ () {}
_ (int mx, int cnt) :mx(mx),cnt(cnt),tag() {}
_ operator + (const _ &rhs) const {
if (mx<rhs.mx) return _(rhs.mx,rhs.cnt);
if (mx>rhs.mx) return _(mx,cnt);
return _(mx,cnt+rhs.cnt);
}
void add(int k) {
mx+=k, tag+=k;
}
} v[N<<]; void dfs(int x) {
if (x>) return;
s[++*s]=x;
dfs(x*+),dfs(x*+);
} void build(int o, int l, int r) {
if (l==r) {
int t;
scanf("%d", &t);
int id = lower_bound(s+,s++*s,t)-s;
v[o]=_(t-s[id],);
a[l]=id;
return;
}
build(ls),build(rs);
v[o]=v[lc]+v[rc];
} void pd(int o) {
if (v[o].tag) {
v[lc].add(v[o].tag);
v[rc].add(v[o].tag);
v[o].tag=;
}
} void upd(int o, int l, int r) {
if (v[o].mx<=) return;
if (l==r) {
while (v[o].mx>) {
v[o].mx -= s[a[l]+]-s[a[l]];
++a[l];
}
return;
}
pd(o),upd(ls),upd(rs);
v[o]=v[lc]+v[rc];
} void add(int o, int l, int r, int k) {
if (ql<=l&&r<=qr) return v[o].add(k),upd(o,l,r);
pd(o);
if (mid>=ql) add(ls,k);
if (mid<qr) add(rs,k);
v[o]=v[lc]+v[rc];
} _ qry(int o, int l, int r) {
if (ql<=l&&r<=qr) return v[o];
pd(o);
if (mid<ql) return qry(rs);
if (mid>=qr) return qry(ls);
return qry(ls)+qry(rs);
} int main() {
dfs(),dfs();
sort(s+,s++*s),*s=unique(s+,s++*s)-s-;
s[++*s]=INF;
scanf("%d%d", &n, &m);
build(,,n);
REP(i,,m) {
int k;
char op[];
scanf("%s%d%d", op, &ql, &qr);
if (*op=='a') scanf("%d", &k), add(,,n,k);
else {
_ ret = qry(,,n);
printf("%d\n",ret.mx?:ret.cnt);
}
}
}