首页 > 代码库 > Rikka with Sequence

Rikka with Sequence

2024-09-09 06:01:43   218人阅读

题意：

给一长度为n的序列，维护三个操作：区间开根，区间加，区间求和。

 

解法：

注意到本题关键在于区间开根：

对于一个数字，只要进行$O(loglogT)$次开根即会变为1。

考虑线段树，对于线段数上的点维护$maxv$，$minv$。

对于$[\sqrt{maxv}] = [\sqrt{minv}]$的点我们直接执行区间染色。

如果我们在开根时经过这个点则有$maxv - minv$减小，且只会经过$O(loglog(maxv-minv))$次。

考虑区间加的操作，相当于只是让$O(logn)$个位于 线段树上 修改区间边界上的两条链上的点 的$maxv-minv$增大，

这样会产生$O(logn*loglog(maxv-minv))$次的后续操作

注意到可能会出现开根后差值不变的情况，这样会导致 线段树上 修改区间内 的点的$maxv-minv$可能不变

导致效率退化。

特判一下，并将其转化为区间加上$\sqrt{maxv} - maxv$。

维护两个标记$addv$与$setv$，$setv$标记优先级大。

这样，总效率$O(nlogn*loglogn)$

 

技术分享 
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 
  6 #define N 100010
  7 #define LL long long
  8 #define l(x) ch[x][0]
  9 #define r(x) ch[x][1]
 10 
 11 using namespace std;
 12 
 13 int n,m,totn;
 14 int a[N];
 15 int ch[N<<1][2];
 16 LL addv[N<<1],maxv[N<<1],minv[N<<1],sumv[N<<1],setv[N<<1];
 17 
 18 void push(int x,int l,int r)
 19 {
 20     if(l==r) return;
 21     int mid=(l+r)>>1;
 22     LL lsiz = (mid-l+1);
 23     LL rsiz = (r-mid);
 24     if(setv[x])
 25     {
 26         setv[l(x)]=setv[x];
 27         maxv[l(x)]=setv[x];
 28         minv[l(x)]=setv[x];
 29         addv[l(x)]=0;
 30         sumv[l(x)]=lsiz*setv[x];
 31         
 32         setv[r(x)]=setv[x];
 33         maxv[r(x)]=setv[x];
 34         minv[r(x)]=setv[x];
 35         addv[r(x)]=0;
 36         sumv[r(x)]=rsiz*setv[x];
 37         setv[x]=0;
 38     }
 39     if(addv[x])
 40     {
 41         if(setv[l(x)]) setv[l(x)]+=addv[x];
 42         else addv[l(x)]+=addv[x];
 43         maxv[l(x)]+=addv[x];
 44         minv[l(x)]+=addv[x];
 45         sumv[l(x)]+=lsiz*addv[x];
 46         
 47         if(setv[r(x)]) setv[r(x)]+=addv[x];
 48         else addv[r(x)]+=addv[x];
 49         maxv[r(x)]+=addv[x];
 50         minv[r(x)]+=addv[x];
 51         sumv[r(x)]+=rsiz*addv[x];
 52         addv[x]=0;
 53     }
 54 }
 55 
 56 void update(int x)
 57 {
 58     maxv[x] = max(maxv[l(x)], maxv[r(x)]);
 59     minv[x] = min(minv[l(x)], minv[r(x)]);
 60     sumv[x] = sumv[l(x)] + sumv[r(x)];
 61 }
 62 
 63 int build(int l,int r)
 64 {
 65     int x=++totn;
 66     addv[x]=0;
 67     setv[x]=0;
 68     if(l==r)
 69     {
 70         maxv[x]=a[l];
 71         minv[x]=a[l];
 72         sumv[x]=a[l];
 73         return x;
 74     }
 75     int mid=(l+r)>>1;
 76     l(x)=build(l,mid);
 77     r(x)=build(mid+1,r);
 78     update(x);
 79     return x;
 80 }
 81 
 82 void solve(int x,int l,int r)
 83 {
 84     push(x,l,r);
 85     if(maxv[x]==1) return;
 86     LL tmp1 = (LL)sqrt(maxv[x]+0.5);
 87     LL tmp2 = (LL)sqrt(minv[x]+0.5);
 88     if(tmp1==tmp2)
 89     {
 90         setv[x]=tmp1;
 91         maxv[x]=tmp1;
 92         minv[x]=tmp1;
 93         sumv[x]=(r-l+1LL)*tmp1;
 94         return;
 95     }
 96     if(maxv[x]==minv[x]+1 && tmp1==tmp2+1)
 97     {
 98         addv[x]=tmp1-maxv[x];
 99         maxv[x]+=addv[x];
100         minv[x]+=addv[x];
101         sumv[x]+=(r-l+1LL)*addv[x];
102         return;
103     }
104     int mid=(l+r)>>1;
105     solve(l(x),l,mid);
106     solve(r(x),mid+1,r);
107     update(x);
108 }
109 
110 void change(int x,int l,int r,int ql,int qr)
111 {
112     push(x,l,r);
113     if(ql<=l && r<=qr)
114     {
115         solve(x,l,r);
116         return;
117     }
118     int mid=(l+r)>>1;
119     if(ql<=mid) change(l(x),l,mid,ql,qr);
120     if(mid<qr) change(r(x),mid+1,r,ql,qr);
121     update(x);
122 }
123 
124 void add(int x,int l,int r,int ql,int qr,LL qv)
125 {
126     push(x,l,r);
127     if(ql<=l && r<=qr)
128     {
129         addv[x]=qv;
130         maxv[x]+=qv;
131         minv[x]+=qv;
132         sumv[x]+=qv*(r-l+1LL);
133         return;
134     }
135     int mid=(l+r)>>1;
136     if(ql<=mid) add(l(x),l,mid,ql,qr,qv);
137     if(mid<qr) add(r(x),mid+1,r,ql,qr,qv);
138     update(x);
139 }
140 
141 LL qsum(int x,int l,int r,int ql,int qr)
142 {
143     push(x,l,r);
144     if(ql<=l && r<=qr) return sumv[x];
145     int mid=(l+r)>>1;
146     LL ans=0;
147     if(ql<=mid) ans+=qsum(l(x),l,mid,ql,qr);
148     if(mid<qr) ans+=qsum(r(x),mid+1,r,ql,qr);
149     update(x);
150     return ans;
151 }
152 
153 int main()
154 {
155     while(~scanf("%d%d",&n,&m))
156     {
157         totn=0;
158         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
159         build(1,n);
160         int cmd,l,r,x;
161         for(int i=1;i<=m;i++)
162         {
163             scanf("%d%d%d",&cmd,&l,&r);
164             if(cmd==1)
165             {
166                 scanf("%d",&x);
167                 add(1,1,n,l,r,x);
168             }
169             else if(cmd==2) change(1,1,n,l,r);
170             else printf("%lld\n",qsum(1,1,n,l,r));
171         }
172     }
173     return 0;
174 }
View Code

 

Rikka with Sequence


联系
我们