近期做的有意思的两道题，不知道是谁抄谁hhhhh

一道题出在codeforces上，一道题出在牛客的寒假训练营中，今天补题的时候发现两道题趋近于一致

都考察到两个点：找规律（某一函数的性质），set或是线段树维护序列

链接如下

https://codeforces.com/contest/1791/problem/F

https://ac.nowcoder.com/acm/contest/46800/G

都是在对某一序列的在线修改，同时会询问序列的一些特征，如最大值，和等

解题关键在于，虽然题目给出的在线修改次数很多，但实际上，当处理到一定次数时，修改前后的元素大小不变，这就给了操作空间，对于无论如何修改都不会改变大小的元素，我们就不再修改，这样将大大减小运行时间。

codefoeces这道题中，当元素 a < 10，a的大小将不再改变，而在牛客中存在这样的性质 f(x) = x，当且仅当 x = 0 / 99 / 100

有两种解决方案

1.用set维护待操作数的下标，当某一数字已不需要修改，将其下标删除，但是似乎并不容易去维护记录序列的最大值？

　　如果要维护某一序列的最大值，感觉不是很好实现？

2.用线段树去维护，而且懒标记的存在使得在每次询问操作只包含一个区间时可以再次大大优化效率，同时也比较适合用树的结构去维护序列的某一性质，且效率极高

codeforces用的是线段树，而牛客用的是set

但是如果修改次数过多，还是set比较吃香

还有一件事：迭代器的调用太慢了，需要在得到所需要的迭代器后，建一个变量储存迭代器对应的值，不让会TLE

CodeForces：

#include<bits/stdc++.h>

const int MAXN = 2e5 + 10;
using namespace std;

int T;
int n,Q;
struct segtree
{
    int l,r;
    int lazy;
    int num;
}k[MAXN<<2];
int a[MAXN];
int ch;
int x,y;

void build(int l,int r,int rt)
{
    if(l == r)
    {
        k[rt].l = k[rt].r = l;
        k[rt].num = a[l];
        return ;
    }
    k[rt].l = l;
    k[rt].r = r;
    int mid = l + r >> 1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    return ;
}

void pushdown(int rt)
{
    if(k[rt].lazy)
    {
        k[rt<<1].lazy += k[rt].lazy;
        k[rt<<1|1].lazy += k[rt].lazy;
        k[rt].lazy = 0;
    }
    return ;
}

void update(int l,int r,int rt)
{
    if(l > k[rt].r || r < k[rt].l) return ;
    if(l <= k[rt].l && r >= k[rt].r)
    {
        k[rt].lazy++;
        return;
    } 
    int mid = k[rt].l + k[rt].r >> 1;
    if(l <= mid) update(l,r,rt<<1);
    if(r > mid) update(l,r,rt<<1|1);
    return ;
}

int fj(int x)
{
    int res = 0;
    while(x)
    {
        res += x % 10;
        x /= 10;
    }
    return res;
}
int getans(int goal,int rt)
{
    if(k[rt].l == k[rt].r && k[rt].l == goal)
    {
        int cnt = 0;
        while(k[rt].num >= 10 && cnt < k[rt].lazy)
        {
            k[rt].num = fj(k[rt].num);
            cnt++;
        }
        k[rt].lazy = 0;
        return k[rt].num;
    }
    pushdown(rt);
    int mid = k[rt].l + k[rt].r >> 1;
    if(goal <= mid) return getans(goal,rt<<1);
    if(goal > mid) return getans(goal,rt<<1|1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>T;
    while(T--)
    {
        cin>>n>>Q;
        memset(k,0,sizeof k);
        for(int i=1;i<=n;i++) cin>>a[i];
        build(1,n,1);
        for(int i=1;i<=Q;i++)
        {
            cin>>ch;
            if(ch == 1)
            {
                cin>>x>>y;
                update(x,y,1);
            }
            else 
            {
                cin>>x;
                cout<<getans(x,1)<<'\n';
            }
        }
    }
}

牛客：

 1 #include<bits/stdc++.h>
 2 
 3 typedef long long LL;
 4 const int MAXN = 1e5 + 10;
 5 using namespace std;
 6 
 7 int n,m;
 8 int a[MAXN];
 9 int op,l,r,p;
10 LL summ;
11 set <int> k;
12 
13 int main()
14 {
15     ios::sync_with_stdio(false);
16     cin.tie(0);
17     
18     cin>>n>>m;
19     for(int i=1;i<=n;i++){
20         cin>>a[i];
21         summ += a[i];
22         if(a[i] != 0 && a[i] != 99 && a[i] != 100)
23             k.insert(i);
24     }
25 
26     for(int i=1;i<=m;i++)
27     {
28         cin>>op;
29         if(op == 1)
30         {
31             cin>>l>>r>>p;
32             int goal = l;
33             set<int>::iterator it = k.lower_bound(goal);
34             while(*it <= r && it != k.end())
35             {
36                 it = k.lower_bound(goal);    
37                 if(*it > r || it == k.end()) break ;            
38                 int ori = a[*it];
39                 int poi = *it;
40                 while(cnt--)
41                 {
42                     a[poi] = round(10 * sqrt(a[poi]));
43                     if(a[poi] == 0 || a[poi] == 99 || a[poi] == 100) break ;
44                 }
45                 summ += a[poi] - ori;
46                 if(a[poi] == 0 || a[poi] == 99 || a[poi] == 100) k.erase(poi); 
47                 goal = poi + 1;
48             } 
49         }
50         else cout<<summ<<"\n";
51     }
52     return 0;
53 }