Lucky Array CodeForces - 121E (线段树,好题)

题目链接

题目大意:

定义只含数字$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);

         }

     }

 }