P4145

Aryper · 2021-08-14 08:35:08 · 个人记录

上帝造题的七分钟 2 / 花神游历各国

似乎考验了乱搞的能力。

首先，10^{12} 最多开根 6 次就变成 1 了。

也就是说，每个点被修改后会发生变化的修改次数是极有限的。

那么我们感一件非常暴力的事情，建立一个并查集，一个树状数组，一开始暴力修改点，修改后为 1 或 0 的我们以后就不用再修改这个点了，那么我们把它与下一个点用并查集合并，下次修改再遇到的时候直接通过并查集跳到其祖先即可。

时间复杂度 O(m\log n)，修改的复杂度比较玄学，但可以预想到是不会太大的。

当然，利用这个思路也可以用线段树，全 1 或 0 的区间打上标记，以后遇到不再修改，同样也可以达到效果，不过就显得常规了。

代码（树状数组）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;

const ll N=1e6;

ll n,m,op,l,r,x;

ll fa[N+5],a[N+5],c[N+5];

void add(ll x,ll y) {
    for(;x<=n;x+=x&-x) c[x]+=y;
}

ll ask(ll x) {
    ll res=0;
    for(;x;x-=x&-x) res+=c[x];
    return res;
}

ll find(ll x) {
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

void uni(ll x,ll y) {
    fa[find(x)]=find(y);
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        a[i]=read();add(i,a[i]);
        fa[i]=i;
    }

    m=read();

    while(m--) {
        op=read();l=read();r=read();
        if(l>r) swap(l,r);
        if(op==0) {
            x=l;
            while(x<=r) {
            //  printf("test: x=%lld\n",x);
                while(a[x]<=1) {
                    uni(x,x+1);x=fa[x];
                }
                if(x>r) break;
                add(x,-a[x]);a[x]=(ll)sqrt(a[x]);
                add(x,a[x]);x++;
            }
        }
        if(op==1) {
            write(ask(r)-ask(l-1));
            putchar('\n');
        }
//      printf("test:\n");
//      for(ll i=1;i<=n;i++) {
//          printf("%lld ",ask(i)-ask(i-1));
//      }
//      printf("\n");
    }

    return 0;
}