1005: 瑣碎的區間

時間限制:?4 Sec??內存限制:?256 MB

題目描述

給出一個長度為 n 的整數序列 A[1..n]，有三種操作：?
1 l r x : ?把[l, r]區間的每個數都加上 x?
2 l r : ?把[l, r] ?區間每個 A[i]變為sqrt(a[i])的整數部分
3 l r : ?求[l, r] ?區間所有數的和?
其中 l 和 r 和 x 都代表一個整數?

輸入

第一行一個 T，表示數據組數。?
對于每組數據?
Line1：兩個數 n m，表示整數序列長度和操作數?
Line2：n 個數，表示 A[1..n]?
Line3…Line3+m-1：每行一個詢問，對于第三種詢問，請輸出答案。?
對于每一種詢問，先給出操作的編號，再給出相應的操作，編號與題目描述對應。?
數據約定：?
1<=T<=5?
n,m <= 100000?
1<= A[i], x<=100000?

輸出

對于第三種詢問，輸出答案。每個答案占一行。?

樣例輸入

1 5 5 1 2 3 4 5 1 3 5 2 2 1 4 3 2 4 2 3 5 3 1 5

樣例輸出

5 6
分析：
　　　考慮到區間內數不斷開根會導致區間內數越來越接近；
　　　那么可以線段樹維護區間最大值及最小值，一旦區間最大值=區間最小值，那么可以打上延遲標記；
　　　另外可能存在區間開根前與開根后最大值與最小值始終差1，也可以打延遲優化一下；
　　　并且延遲開根標記可以寫成差的形式，那么就只用一個標記即可；
代碼：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <climits> #include <cstring> #include <string> #include <set> #include <bitset> #include <map> #include <queue> #include <stack> #include <vector> #include <cassert> #include <ctime> #define rep(i,m,n) for(i=m;i<=n;i++) #define mod 1000000009 #define inf 0x3f3f3f3f #define vi vector<int> #define pb push_back #define mp make_pair #define fi first #define se second #define ll long long #define pi acos(-1.0) #define pii pair<int,int> #define sys system("pause") const int maxn=1e5+10; const int N=2e5+10; using namespace std; #define ls rt<<1 #define rs rt<<1|1 ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;} int n,m,k,t,a[maxn]; ll tag[maxn<<2],ma[maxn<<2],mi[maxn<<2],sum[maxn<<2]; const int BufferSize=1<<16; char buffer[BufferSize],*head,*tail; inline char Getchar() {if(head==tail) {int l=fread(buffer,1,BufferSize,stdin);tail=(head=buffer)+l;}return *head++; } inline int read() {int x=0,f=1;char c=Getchar();for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;for(;isdigit(c);c=Getchar()) x=x*10+c-'0';return x*f; } void pup(int l,int r,int rt) {int mid=l+r>>1;sum[rt]=sum[ls]+sum[rs];ma[rt]=max(ma[ls],ma[rs]);mi[rt]=min(mi[ls],mi[rs]);tag[rt]=0; } void pdw(int l,int r,int rt) {int mid=l+r>>1;sum[ls]+=tag[rt]*(mid-l+1);ma[ls]+=tag[rt];mi[ls]+=tag[rt];tag[ls]+=tag[rt];sum[rs]+=tag[rt]*(r-mid);ma[rs]+=tag[rt];mi[rs]+=tag[rt];tag[rs]+=tag[rt];tag[rt]=0; } void build(int l,int r,int rt) {if(l==r){tag[rt]=0;ma[rt]=mi[rt]=sum[rt]=a[l];return;}int mid=l+r>>1;build(l,mid,ls);build(mid+1,r,rs);pup(l,r,rt); } void upd(int L,int R,ll v,int l,int r,int rt) {if(L<=l&&r<=R){sum[rt]+=v*(r-l+1);ma[rt]+=v;mi[rt]+=v;tag[rt]+=v;return;}int mid=l+r>>1;if(tag[rt])pdw(l,r,rt);if(L<=mid)upd(L,R,v,l,mid,ls);if(R>mid)upd(L,R,v,mid+1,r,rs);pup(l,r,rt); } void qsqrt(int L,int R,int l,int r,int rt) {if(L<=l&&r<=R){if(ma[rt]==mi[rt]){tag[rt]-=ma[rt];ma[rt]=sqrt(ma[rt]);tag[rt]+=ma[rt];mi[rt]=ma[rt];sum[rt]=(r-l+1)*ma[rt];return;}else if(ma[rt]==mi[rt]+1){if((ll)sqrt(ma[rt])==(ll)sqrt(mi[rt])+1){tag[rt]-=ma[rt];sum[rt]-=(r-l+1)*(ma[rt]-(ll)sqrt(ma[rt]));ma[rt]=sqrt(ma[rt]);tag[rt]+=ma[rt];mi[rt]=ma[rt]-1;return;}}}int mid=l+r>>1;if(tag[rt])pdw(l,r,rt);if(L<=mid)qsqrt(L,R,l,mid,ls);if(R>mid)qsqrt(L,R,mid+1,r,rs);pup(l,r,rt); } ll gao(int L,int R,int l,int r,int rt) {if(L<=l&&r<=R)return sum[rt];int mid=l+r>>1;if(tag[rt])pdw(l,r,rt);ll ret=0;if(L<=mid)ret+=gao(L,R,l,mid,ls);if(R>mid)ret+=gao(L,R,mid+1,r,rs);return ret; } int main() {int i,j;t=read();while(t--){n=read();m=read();rep(i,1,n)a[i]=read();build(1,n,1);while(m--){int b,c,d,e;b=read(),c=read(),d=read();if(b==1){e=read();upd(c,d,e,1,n,1);}else if(b==2){qsqrt(c,d,1,n,1);}else printf("%lld\n",gao(c,d,1,n,1));}}return 0; }

轉載于:https://www.cnblogs.com/dyzll/p/6794089.html

總結

以上是生活随笔為你收集整理的琐碎的区间的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。