【Educational Codeforces Round 37 F】SUM and REPLACE

在这里输入题意

【题解】

那个D函数它的下降速度是很快的。
也就是说到最后他会很快的变成2或者1
而D(2)==2,D(1)=1
也就是说,几次操作过后很多数字实际上就不会发生变化了。
我们可以以这个为切入点。

可以用树状数组写,也可以用线段树写。

如果用树状数组写的话。

你需要额外用一个set来维护哪些值是还能变化的。

然后在读入l,r这个范围的时候。

直接用lower_bound查找离它最近的且大于等于它的能改变的值。

将它改变。

然后在树状数组中改变对应位置的值。

如果发现改变之后这个数字变成小于等于2了。

那么就在set中删掉这个值。

这样的话.下次在遍历的时候就不会再找到这个值了。

求和的话,还是用树状数组的求和就好了。

如果用线段树的话。

在改变的时候。

直到l==r的时候再改变。

然后维护一个区间的最大值和区间和。

如果区间的最大值<=2那么直接返回这个区间的和就好了。

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e6;

const int NN = 3e5;

struct BI {

	ll a[NN + 10];

	int lowbit(int x) {

		return x&(-x);

	}

	void add(int x,int y) {

		while (x <= NN) {

			a[x] += y;

			x += lowbit(x);

		}

	}

	ll sum(int x) {

		ll now = 0;

		while (x > 0) {

			now += a[x];

			x -= lowbit(x);

		}

		return now;

	}

	ll get_sum(int l, int r) {

		return sum(r) - sum(l - 1);

	}

}b;

int f[N+10],n,m,a[NN+10];

set<int> myset;

vector<int> V;

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    for (int i = 1;i <= N;i++)

            for (int j = i;j <= N;j+=i)

                f[j]++;

    cin >> n >> m;

    for (int i = 1;i <= n;i++) {

        cin >> a[i];

        myset.insert(i);

        b.add(i,a[i]);

    }

    for (int i = 1;i <= m;i++){

        int ope,l,r;

        cin >> ope >> l >> r;

        if (ope==1){

            V.clear();

            while (1){

                auto t = myset.lower_bound(l);

                if (t==myset.end()||(*t)>r) break;

                V.push_back(*t);

                myset.erase(t);

            }

            for (int x:V){

                b.add(x,f[a[x]]-a[x]);

                a[x] = f[a[x]];

                if (a[x]<=2) continue;

                myset.insert(x);

            }

        }else{

            cout<<b.get_sum(l,r)<<endl;

        }

    }

	return 0;

}

巴特西

【Educational Codeforces Round 37 F】SUM and REPLACE

最新文章

热门文章