1005: 琐碎的区间
时间限制: 4 Sec 内存限制: 256 MB提交: 100 解决: 10
[提交][状态][讨论版]
题目描述
给出一个长度为 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
输出
对于第三种询问,输出答案。每个答案占一行。
样例输入
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 <bits/stdc++.h> 2 3 #define ll long long 4 const int maxn=1e5+10; 5 const int N=2e5+10; 6 using namespace std; 7 #define ls rt<<1 8 #define rs rt<<1|1 9 int n,m,k,t,a[maxn]; 10 ll tag[maxn<<2],ma[maxn<<2],mi[maxn<<2],sum[maxn<<2]; 11 const int BufferSize=1<<16; 12 char buffer[BufferSize],*head,*tail; 13 inline char Getchar() { 14 if(head==tail) { 15 int l=fread(buffer,1,BufferSize,stdin); 16 tail=(head=buffer)+l; 17 } 18 return *head++; 19 } 20 inline int read() { 21 int x=0,f=1;char c=Getchar(); 22 for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1; 23 for(;isdigit(c);c=Getchar()) x=x*10+c-'0'; 24 return x*f; 25 } 26 void pup(int l,int r,int rt) 27 { 28 int mid=l+r>>1; 29 sum[rt]=sum[ls]+sum[rs]; 30 ma[rt]=max(ma[ls],ma[rs]); 31 mi[rt]=min(mi[ls],mi[rs]); 32 tag[rt]=0; 33 } 34 void pdw(int l,int r,int rt) 35 { 36 int mid=l+r>>1; 37 sum[ls]+=tag[rt]*(mid-l+1); 38 ma[ls]+=tag[rt]; 39 mi[ls]+=tag[rt]; 40 tag[ls]+=tag[rt]; 41 sum[rs]+=tag[rt]*(r-mid); 42 ma[rs]+=tag[rt]; 43 mi[rs]+=tag[rt]; 44 tag[rs]+=tag[rt]; 45 tag[rt]=0; 46 } 47 void build(int l,int r,int rt) 48 { 49 if(l==r) 50 { 51 tag[rt]=0; 52 ma[rt]=mi[rt]=sum[rt]=a[l]; 53 return; 54 } 55 int mid=l+r>>1; 56 build(l,mid,ls); 57 build(mid+1,r,rs); 58 pup(l,r,rt); 59 } 60 void upd(int L,int R,ll v,int l,int r,int rt) 61 { 62 if(L<=l&&r<=R) 63 { 64 sum[rt]+=v*(r-l+1); 65 ma[rt]+=v; 66 mi[rt]+=v; 67 tag[rt]+=v; 68 return; 69 } 70 int mid=l+r>>1; 71 if(tag[rt])pdw(l,r,rt); 72 if(L<=mid)upd(L,R,v,l,mid,ls); 73 if(R>mid)upd(L,R,v,mid+1,r,rs); 74 pup(l,r,rt); 75 } 76 void qsqrt(int L,int R,int l,int r,int rt) 77 { 78 if(L<=l&&r<=R) 79 { 80 if(ma[rt]==mi[rt]) 81 { 82 tag[rt]-=ma[rt]; 83 ma[rt]=sqrt(ma[rt]); 84 tag[rt]+=ma[rt]; 85 mi[rt]=ma[rt]; 86 sum[rt]=(r-l+1)*ma[rt]; 87 return; 88 } 89 else if(ma[rt]==mi[rt]+1) 90 { 91 if((ll)sqrt(ma[rt])==(ll)sqrt(mi[rt])+1) 92 { 93 tag[rt]-=ma[rt]; 94 sum[rt]-=(r-l+1)*(ma[rt]-(ll)sqrt(ma[rt])); 95 ma[rt]=sqrt(ma[rt]); 96 tag[rt]+=ma[rt]; 97 mi[rt]=ma[rt]-1; 98 return; 99 } 100 } 101 } 102 int mid=l+r>>1; 103 if(tag[rt])pdw(l,r,rt); 104 if(L<=mid)qsqrt(L,R,l,mid,ls); 105 if(R>mid)qsqrt(L,R,mid+1,r,rs); 106 pup(l,r,rt); 107 } 108 ll gao(int L,int R,int l,int r,int rt) 109 { 110 if(L<=l&&r<=R)return sum[rt]; 111 int mid=l+r>>1; 112 if(tag[rt])pdw(l,r,rt); 113 ll ret=0; 114 if(L<=mid)ret+=gao(L,R,l,mid,ls); 115 if(R>mid)ret+=gao(L,R,mid+1,r,rs); 116 return ret; 117 } 118 int main() 119 { 120 t=read(); 121 while(t--) 122 { 123 n=read();m=read(); 124 for(int i=1;i<=n;i++) 125 a[i]=read(); 126 build(1,n,1); 127 while(m--) 128 { 129 int b,c,d,e; 130 b=read(),c=read(),d=read(); 131 if(b==1) 132 { 133 e=read(); 134 upd(c,d,e,1,n,1); 135 } 136 else if(b==2) 137 { 138 qsqrt(c,d,1,n,1); 139 } 140 else printf("%lld ",gao(c,d,1,n,1)); 141 } 142 } 143 return 0; 144 }
超时代码,
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int BufferSize=1<<16; 5 char buffer[BufferSize],*head,*tail; 6 inline char Getchar() { 7 if(head==tail) { 8 int l=fread(buffer,1,BufferSize,stdin); 9 tail=(head=buffer)+l; 10 } 11 return *head++; 12 } 13 14 inline int read() { 15 int x=0,f=1;char c=Getchar(); 16 for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1; 17 for(;isdigit(c);c=Getchar()) x=x*10+c-'0'; 18 return x*f; 19 } 20 21 #define LL long long 22 23 #define L(root) ((root) << 1) 24 #define R(root) (((root) << 1) | 1) 25 26 const int MAXN = 1e5 + 5; 27 int numbers[MAXN]; 28 29 //LL delay[MAXN * 4], sum[MAXN * 4], mx[MAXN * 4], mn[MAXN * 4]; 30 31 struct Node { 32 int left, right; 33 LL delay; 34 LL sum; 35 LL mx, mn; 36 int mid() 37 { 38 return left + ((right - left) >> 1); 39 } 40 } tree[MAXN * 4]; 41 42 void pushUp(int root) 43 { 44 tree[root].sum = tree[L(root)].sum + tree[R(root)].sum; 45 tree[root].mx = max(tree[L(root)].mx, tree[R(root)].mx); 46 tree[root].mn = min(tree[L(root)].mn, tree[R(root)].mn); 47 tree[root].delay = 0; 48 } 49 50 void pushDown(int root, int l, int r) 51 { 52 LL mid = (r + l) >> 1; 53 tree[L(root)].delay += tree[root].delay; 54 tree[R(root)].delay += tree[root].delay; 55 tree[L(root)].sum += tree[root].delay * (mid - l + 1); 56 tree[R(root)].sum += tree[root].delay * (r - mid); 57 tree[L(root)].mx += tree[root].delay; 58 tree[R(root)].mx += tree[root].delay; 59 tree[L(root)].mn += tree[root].delay; 60 tree[R(root)].mn += tree[root].delay; 61 tree[root].delay = 0; 62 63 } 64 65 void build(int root, int left, int right) 66 { 67 tree[root].left = left; 68 tree[root].right = right; 69 if (left == right) { 70 tree[root].delay = 0; 71 tree[root].sum = numbers[left]; 72 tree[root].mx = numbers[left]; 73 tree[root].mn = numbers[left]; 74 return; 75 } 76 int mid = tree[root].mid(); 77 build(L(root), left, mid); 78 build(R(root), mid + 1, right); 79 pushUp(root); 80 } 81 82 LL query(int root, int left, int right) 83 { 84 if (tree[root].left == left && tree[root].right == right) { 85 return tree[root].sum; 86 } 87 if (tree[root].delay) pushDown(root, tree[root].left, tree[root].right); 88 int mid = tree[root].mid(); 89 if (right <= mid) { 90 return query(L(root), left, right); 91 } else if (left > mid) { 92 return query(R(root), left, right); 93 } else { 94 return query(L(root), left, mid) + query(R(root), mid + 1, right); 95 } 96 } 97 98 void update(int root, int left, int right, LL add) 99 { 100 if (tree[root].left == left && tree[root].right == right) { 101 tree[root].delay += add; 102 tree[root].sum += add * (right - left + 1); 103 tree[root].mx += add; 104 tree[root].mn += add; 105 return; 106 } 107 if (tree[root].delay) pushDown(root, tree[root].left, tree[root].right); 108 int mid = tree[root].mid(); 109 if (right <= mid) { 110 update(L(root), left, right, add); 111 } else if (left > mid) { 112 update(R(root), left, right, add); 113 } else { 114 update(L(root), left, mid, add); 115 update(R(root), mid + 1, right, add); 116 } 117 pushUp(root); 118 } 119 120 void sq(int root, int left, int right) 121 { 122 if (tree[root].left == left && tree[root].right == right) { 123 LL mx = sqrt(tree[root].mx); 124 LL mn = sqrt(tree[root].mn); 125 if (tree[root].mx == tree[root].mn) { 126 tree[root].delay -= (tree[root].mx - mx); 127 tree[root].sum = mx * (right - left + 1); 128 tree[root].mx = mx; 129 tree[root].mn = mn; 130 return; 131 // } 132 } else if ((tree[root].mx == tree[root].mn + 1) && (mx == mn + 1)) { 133 tree[root].delay -= (tree[root].mx - mx); 134 tree[root].sum -= (tree[root].mx - mx) * (right - left + 1); 135 tree[root].mx = mx; 136 tree[root].mn = mn; 137 } 138 } 139 if (tree[root].delay) pushDown(root, tree[root].left, tree[root].right); 140 int mid = tree[root].mid(); 141 if (right <= mid) { 142 sq(L(root), left, right); 143 } else if (left > mid) { 144 sq(R(root), left, right); 145 } else { 146 sq(L(root), left, mid); 147 sq(R(root), mid + 1, right); 148 } 149 pushUp(root); 150 } 151 152 int main() 153 { 154 int t; 155 int n, m; 156 int i; 157 int op, l, r, x; 158 159 // scanf("%d", &t); 160 t = read(); 161 while (t--) { 162 // scanf("%d%d", &n, &m); 163 n = read(), m = read(); 164 for (i = 1; i <= n; ++i) { 165 // scanf("%d", &numbers[i]); 166 numbers[i] = read(); 167 } 168 build(1, 1, n); 169 for (i = 0; i < m; ++i) { 170 // scanf("%d", &op); 171 op = read(); 172 if (op == 1) { 173 // scanf("%d%d%d", &l, &r, &x); 174 l = read(), r = read(), x = read(); 175 update(1, l, r, x); 176 //printf("debug op = 1 "); 177 } else if (op == 2) { 178 // scanf("%d%d", &l, &r); 179 l = read(), r = read(); 180 sq(1, l, r); 181 //printf("debug op = 2 "); 182 } else { 183 // scanf("%d%d", &l, &r); 184 l = read(), r = read(); 185 printf("%lld ", query(1, l, r)); 186 //printf("debug op = 3 "); 187 } 188 } 189 } 190 return 0; 191 } 192 193 194 int main2() 195 { 196 int t; 197 int n, m; 198 int i; 199 int op, l, r, x; 200 201 scanf("%d", &t); 202 // t = read(); 203 while (t--) { 204 scanf("%d%d", &n, &m); 205 // n = read(), m = read(); 206 for (i = 1; i <= n; ++i) { 207 scanf("%d", &numbers[i]); 208 // numbers[i] = read(); 209 } 210 build(1, 1, n); 211 for (i = 0; i < m; ++i) { 212 scanf("%d", &op); 213 // op = read(); 214 if (op == 1) { 215 scanf("%d%d%d", &l, &r, &x); 216 // l = read(), r = read(), x = read(); 217 update(1, l, r, x); 218 //printf("debug op = 1 "); 219 } else if (op == 2) { 220 scanf("%d%d", &l, &r); 221 // l = read(), r = read(); 222 sq(1, l, r); 223 //printf("debug op = 2 "); 224 } else { 225 scanf("%d%d", &l, &r); 226 // l = read(), r = read(); 227 printf("%lld ", query(1, l, r)); 228 //printf("debug op = 3 "); 229 } 230 } 231 } 232 return 0; 233 }