首页 > 代码库 > 琐碎的区间
琐碎的区间
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 都代表一个整数
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
对于每组数据
Line1：两个数 n m，表示整数序列长度和操作数
Line2：n 个数，表示 A[1..n]
Line3…Line3+m-1：每行一个询问，对于第三种询问，请输出答案。
对于每一种询问，先给出操作的编号，再给出相应的操作，编号与题目描述对应。
数据约定：
1<=T<=5
n,m <= 100000
1<= A[i], x<=100000
输出
对于第三种询问，输出答案。每个答案占一行。
样例输入
15 51 2 3 4 51 3 5 22 1 43 2 42 3 53 1 5样例输出
56
分析：
考虑到区间内数不断开根会导致区间内数越来越接近；
那么可以线段树维护区间最大值及最小值，一旦区间最大值=区间最小值，那么可以打上延迟标记；
另外可能存在区间开根前与开根后最大值与最小值始终差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|1ll 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;}
琐碎的区间
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。