Description

Solution

树状数组单点修改区间查询

我们知道一个数n最多修改loglogn次就会变为1

并查集维护每个数右边第一个不为1的位置

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 100005using namespace std;typedef long long LL; int n,m,delta[MAXN],father[MAXN];LL c[MAXN]; int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){        if(c=='-')f=-1;c=getchar();    }    while(c>='0'&&c<='9'){        x=x*10+c-'0';c=getchar();    }    return x*f;}int lowbit(int x){
   return x&-x;}void add(int pos,int x){    while(pos<=n)    {        c[pos]+=x;        pos+=lowbit(pos);    }}LL query(int pos){    LL res=0;    while(pos>0)    {        res+=c[pos];        pos-=lowbit(pos);    }    return res;}int find(int x){    if(x==father[x])return x;    father[x]=find(father[x]);    return father[x];}int main(){    n=read();    for(int i=1;i<=n;i++)    {        delta[i]=read();        add(i,delta[i]);        father[i]=i;    }    m=read();    for(int i=1;i<=m;i++)    {        int x=read(),l=read(),r=read();        if(x==1)        printf("%lld\n",query(r)-query(l-1));        else if(x==2)        {            for(int j=l;j<=r&&j;j=find(j+1))            {                add(j,(int)sqrt(delta[j])-delta[j]);                delta[j]=(int)sqrt(delta[j]);                if(delta[j]<=1)father[j]=j+1;            }        }    }    return 0;}