Rikka with Sequence
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5828
Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Yuta has an array A with n numbers. Then he makes m operations on it.
There are three type of operations:
1 l r x : For each i in [l,r], change A[i] to A[i]+x
2 l r : For each i in [l,r], change A[i] to
3 l r : Yuta wants Rikka to sum up A[i] for all i in [l,r]
It is too difficult for Rikka. Can you help her?
Input
The first line contains a number t(11000.
For each testcase, the first line contains two numbers n,m(1
Output
For each operation of type 3, print a lines contains one number -- the answer of the query.
Sample Input
1
5 5
1 2 3 4 5
1 3 5 2
2 1 4
3 2 4
2 3 5
3 1 5
Sample Output
5
6
Source
2016 Multi-University Training Contest 8
##题意：
对一个数组进行若干操作：
1. 将区间内的值都加x.
2. 将区间内的值都开平方.
3. 求区间内数的和.
##题解：
容易想到用线段树来维护，关键是如何处理操作二. 直接对每个数开平方肯定会超时.
考虑到开平方操作的衰减速度很快，一个数最多经过6次开平方操作就会到1.
那么随着操作的进行，区间内的数会趋于相同，恰好利用这个点来作剪枝.
对于树中的每个结点维护一个equal, 表示当前结点的子节点是否相等. (若相等就等于子节点的值，否则为-1).
当更新到某区间时，若区间内的值都相同，则只更新到这里即可，下面的结点利用pushdown来更新.
赛后数据被加强了，上述思路在HDU上已经AC不了了. sad....
##代码：
``` cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-8
#define maxn 101000
#define mod 100000007
#define inf 0x3f3f3f3f
#define mid(a,b) ((a+b)>>1)
#define IN freopen("in.txt","r",stdin);
using namespace std;
int n;
LL num[maxn];
struct Tree
{
int left,right;
LL lazy,sum,equl;
}tree[maxn<<2];
void build(int i,int left,int right)
{
tree[i].left=left;
tree[i].right=right;
tree[i].lazy=0;
if(left==right){
tree[i].sum = num[left];
tree[i].equl = num[left];
return ;
}
int mid=mid(left,right);
build(i<<1,left,mid);
build(i<<1|1,mid+1,right);
tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;
tree[i].equl = tree[i<<1].equl==tree[i<<1|1].equl ? tree[i<<1].equl : -1;
}
void pushdown(int i)
{
if(tree[i].equl != -1) {
tree[i<<1].equl = tree[i].equl;
tree[i<<1|1].equl = tree[i].equl;
tree[i<<1].sum = (tree[i<<1].right-tree[i<<1].left+1)tree[i].equl;
tree[i<<1|1].sum = (tree[i<<1|1].right-tree[i<<1|1].left+1)tree[i].equl;
tree[i].lazy = 0;
tree[i<<1].lazy = 0;
tree[i<<1|1].lazy = 0;
}
if(tree[i].lazy) {
tree[i<<1].lazy += tree[i].lazy;
tree[i<<1|1].lazy += tree[i].lazy;
tree[i<<1].sum += (tree[i<<1].right-tree[i<<1].left+1)tree[i].lazy;
tree[i<<1|1].sum += (tree[i<<1|1].right-tree[i<<1|1].left+1)tree[i].lazy;
if(tree[i<<1].equl != -1) {
tree[i<<1].equl += tree[i].lazy;
tree[i<<1].lazy = 0;
}
if(tree[i<<1|1].equl != -1) {
tree[i<<1|1].equl += tree[i].lazy;
tree[i<<1|1].lazy = 0;
}
tree[i].lazy = 0;
}
}
void update(int i,int left,int right,LL d)
{
if(tree[i].leftleft&&tree[i].rightright)
{
tree[i].sum += (right-left+1)*d;
if(tree[i].equl == -1) tree[i].lazy += d;
else tree[i].equl += d;
return ;
}
pushdown(i);
int mid=mid(tree[i].left,tree[i].right);
if(right<=mid) update(i<<1,left,right,d);
else if(left>mid) update(i<<1|1,left,right,d);
else {
update(i<<1,left,mid,d);
update(i<<1|1,mid+1,right,d);
}
tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;
tree[i].equl = tree[i<<1].equl==tree[i<<1|1].equl ? tree[i<<1].equl : -1;
}
void update_sqrt(int i,int left,int right)
{
if(tree[i].leftleft&&tree[i].rightright && tree[i].equl!=-1)
{
tree[i].equl = (LL)sqrt(tree[i].equl);
tree[i].sum = tree[i].equl * (tree[i].right-tree[i].left+1);
tree[i].lazy = 0;
return ;
}
pushdown(i);
int mid=mid(tree[i].left,tree[i].right);
if(right<=mid) update_sqrt(i<<1,left,right);
else if(left>mid) update_sqrt(i<<1|1,left,right);
else {
update_sqrt(i<<1,left,mid);
update_sqrt(i<<1|1,mid+1,right);
}
tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;
tree[i].equl = tree[i<<1].equl==tree[i<<1|1].equl ? tree[i<<1].equl : -1;
}
LL query(int i,int left,int right)
{
if(tree[i].leftleft&&tree[i].rightright)
return tree[i].sum;
pushdown(i);
int mid=mid(tree[i].left,tree[i].right);
if(right<=mid) return query(i<<1,left,right);
else if(left>mid) return query(i<<1|1,left,right);
else return query(i<<1,left,mid)+query(i<<1|1,mid+1,right);
}
int main(int argc, char const *argv[])
{
//IN;
int t; cin >> t;
while(t--)
{
int m;
scanf("%d %d", &n,&m);
for(int i=1; i<=n; i++)
scanf("%lld", &num[i]);
build(1, 1, n);
while(m--) {
int op, l, r;
scanf("%d %d %d", &op,&l,&r);
if(op == 1) {
LL x; scanf("%lld", &x);
update(1, l, r, x);
}
else if(op == 2) {
update_sqrt(1, l, r);
}
else if(op == 3) {
printf("%lld\n", query(1, l, r));
}
}
}
return 0;
}