CF121E 题解

· · 题解

题目链接。

大体思路：

首先看到这题，很明显是一道数据结构，再一看，很明显的线段树，维护两个操作，区间查询，区间修改，可以维护两个值，一个是加上一个数后的本身的值，一个是是否满足是幸运数字，怎么判断幸运数字呢，当然可以打表了，暴力打表之后欣喜的发现只有 30 个幸运数，具体也很好实现。

但是，有没有更简单的做法呢，当然是树状数组啦。

但是要区间加怎么办，好办，暴力枚举要加的区间就好了。

Q：

为什么这样的复杂度是正确的？

A:

观察题面，不难得到一个性质。“保证所有数操作前后都不超过 1\times10^4。“

这就意味着一个很重要的性质，每个数最多就只会被加 1\times10^4 次，也就是说我们的 add 操作在最坏情况下最多只会做 1\times10^4 次，就算每次给整个区间的值加，也只会达到 1\times10^9 的级别，在四秒的时限下，是可以跑过的，至于查询操作，则是 n\log n 级别，忽略不计了，又如循环内的 add 函数查找，是 \log30 级别，可以忽略不计，常数大小。

（注意，我这里把加小区间的时间忽略了，并且，add 操作可能会进行更多次，但是这也就意味着枚举的区间变小了，整体复杂度均摊下来，最坏 1\times10^9 的级别。）

因此，这里用树状数组是可以很完美的冲过去的，并不存在什么数据水。

代码实现：

自认为马蜂刻毒。

#include <bits/stdc++.h>
using namespace std;
const int N=101010;
int n,m;

int check[100]={0,4,7,44,47,74,77,444,447,474,477,744,747,774,777,4444,4447,4474,4477,4744,4747,4774,4777,7444,7447,7474,7477,7744,7747,7774,7777};
int check2[N];

int tr[N];
int sum[N];
int a[N];
//常规
int lobit(int x){
  return x&-x;
}

int query(int x){
  int res=0;
  while(x){
    res+=tr[x];
    x-=lobit(x);
  }
  return res;
}

void update(int x,int c){
    while(x<=n){
      tr[x]+=c;
      x+=lobit(x);
    }
}
//常规

int main(){
  ios::sync_with_stdio(false);
    cin>>n>>m;

    for(int i=1;i<=30;i++){
      check2[check[i]]=true;
    }//预处理打表数组


    for(int i=1;i<=n;i++){
      cin>>a[i];
      if(check2[a[i]]){
        update(i,1);
      }
    }//如果是幸运数，就加上。

    for(int i=1;i<=m;i++){
      string op;
      cin>>op;
      if(op=="count"){
        int l,r;
        cin>>l>>r;
        cout<<query(r)-query(l-1)<<endl;//直接求区间的前缀和之差就好了
      }
      else{
        int l,r,d;
        cin>>l>>r>>d;
        for(int i=l;i<=r;i++){
          int x=a[i]+d;
          if(check2[a[i]]){//之前有的消去，加上一个数后原数不一定是幸运数
            update(i,-1);
          }
          a[i]+=d;
          if(check2[x]){//是就加上
            update(i,1);  
          }
        }
      }
    }
    return 0;
}