判断相同区间(lazy) 多校8 HDU 5828 Rikka with Sequence

  1 // 判断相同区间(lazy) 多校8 HDU 5828 Rikka with Sequence
  2 // 题意：三种操作，1增加值，2开根，3求和
  3 // 思路：这题与HDU 4027 和HDU 5634 差不多
  4 // 注意开根号的话，遇到极差等于1的，开根号以后有可能还是差1.如
  5 // 2 3 2 3。。。
  6 // 8 9 8 9。。。
  7 // 2 3 2 3。。。
  8 // 8 9 8 9。。。
  9 // 剩下就是遇到区间相等的话，就直接开根号不往下传
 10 
 11 
 12 #include <bits/stdc++.h>
 13 using namespace std;
 14 #define LL long long
 15 const int inf = 0x3f3f3f3f;
 16 const int MOD =998244353; 
 17 const int N =1e5+10; 
 18 #define clc(a,b) memset(a,b,sizeof(a))
 19 const double eps = 1e-7;
 20 void fre(){freopen("in.txt","r",stdin);}
 21 void freout() {freopen("out.txt","w",stdout);}
 22 inline int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}
 23 int n,q;
 24 int a[N];
 25 struct node{
 26     int l,r,len;
 27     LL sum,lazy;
 28     LL mx,mn;
 29 }t[N<<2];
 30 
 31 void pushup(int rt){
 32     t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;
 33     t[rt].mx=max(t[rt<<1].mx,t[rt<<1|1].mx);
 34     t[rt].mn=min(t[rt<<1|1].mn,t[rt<<1].mn);
 35 }
 36 void pushdown(int rt){
 37     if(t[rt].lazy){
 38         t[rt<<1].lazy+=t[rt].lazy;
 39         t[rt<<1].mx+=t[rt].lazy;
 40         t[rt<<1].mn+=t[rt].lazy;
 41         t[rt<<1].sum+=t[rt<<1].len*t[rt].lazy;
 42         t[rt<<1|1].lazy+=t[rt].lazy;
 43         t[rt<<1|1].mx+=t[rt].lazy;
 44         t[rt<<1|1].mn+=t[rt].lazy;
 45         t[rt<<1|1].sum+=t[rt<<1|1].len*t[rt].lazy;
 46         t[rt].lazy=0;
 47     }
 48 }
 49 void build(int rt,int l,int r){
 50     t[rt].l=l;
 51     t[rt].r=r;
 52     t[rt].lazy=0;
 53     t[rt].mx=0;
 54     t[rt].mn=inf;
 55     t[rt].len=r-l+1;
 56     if(l==r){
 57        t[rt].sum=a[l],t[rt].mx=t[rt].mn=a[l];
 58        return;    
 59     }
 60     int mid=(l+r)>>1;
 61     build(rt<<1,l,mid);
 62     build(rt<<1|1,mid+1,r);
 63     pushup(rt);
 64 }
 65 
 66 void update1(int rt,int l,int r,int z){
 67     if(t[rt].l>=l&&t[rt].r<=r){
 68         t[rt].sum+=(LL)t[rt].len*z;
 69         t[rt].lazy+=z;
 70         t[rt].mn+=z;
 71         t[rt].mx+=z;
 72         return;
 73     }
 74     pushdown(rt);
 75     int mid=(t[rt].l+t[rt].r)>>1;
 76     if(r<=mid) update1(rt<<1,l,r,z);
 77     else if(l>mid) update1(rt<<1|1,l,r,z);
 78     else {
 79         update1(rt<<1,l,mid,z);
 80         update1(rt<<1|1,mid+1,r,z);
 81     }
 82     pushup(rt);
 83 }
 84 
 85 void update2(int rt,int l,int r){
 86     if(t[rt].l>=l&&t[rt].r<=r){
 87         if(t[rt].mx==t[rt].mn){
 88            LL tem=(LL)sqrt(t[rt].mx);
 89            t[rt].sum=(LL)tem*t[rt].len;
 90            t[rt].lazy-=(t[rt].mx-tem);
 91            t[rt].mx=t[rt].mn=tem;
 92            return;
 93         }
 94         else if(t[rt].mx==t[rt].mn+1){
 95             LL tem1=(LL)sqrt(t[rt].mx);
 96             LL tem2=(LL)sqrt(t[rt].mn);
 97             if(tem1==tem2+1){
 98                 t[rt].sum-=(LL)(t[rt].mx-tem1)*t[rt].len;
 99                 t[rt].lazy-=(t[rt].mx-tem1);
100                 t[rt].mx=tem1;
101                 t[rt].mn=tem2;
102                 return;
103             }
104         }
105     }
106     pushdown(rt);
107     int mid=(t[rt].l+t[rt].r)>>1;
108     if(r<=mid) update2(rt<<1,l,r);
109     else if(l>mid) update2(rt<<1|1,l,r);
110     else {
111         update2(rt<<1,l,mid);
112         update2(rt<<1|1,mid+1,r);
113     }
114     pushup(rt);
115 }
116 
117 LL query(int rt,int l,int r){
118     if(t[rt].l>=l&&t[rt].r<=r){
119         return t[rt].sum;
120     }
121     pushdown(rt);
122     int mid=(t[rt].l+t[rt].r)>>1;
123     if(r<=mid) return query(rt<<1,l,r);
124     else if(l>mid) return query(rt<<1|1,l,r);
125     else {
126         return query(rt<<1,l,mid)+query(rt<<1|1,mid+1,r);
127     }
128 }
129 int main(){
130     int T;
131     scanf("%d",&T);
132     while(T--){
133        scanf("%d%d",&n,&q);
134        for(int i=1;i<=n;i++) {
135         scanf("%d",&a[i]);
136        }
137        build(1,1,n);
138        while(q--){
139            int op,x,y,z;
140            scanf("%d%d%d",&op,&x,&y);
141            if(op==1){
142                scanf("%d",&z);
143                update1(1,x,y,z);
144            }
145            else if(op==2){
146                update2(1,x,y);
147            } 
148            else {
149                LL ans=query(1,x,y);
150                printf("%I64d
",ans);
151            }
152        }
153     }
154     return 0;
155 }