HDU 5828 Rikka with Sequence （线段树）

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(1<=t<=100), the number of the testcases. And there are no more than 5 testcases with n>1000. For each testcase, the first line contains two numbers n,m(1<=n,m<=100000). The second line contains n numbers A[1]~A[n]. Then m lines follow, each line describe an operation. It is guaranteed that 1<=A[i],x<=100000.

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
", query(1, l, r));
        }
    }
}

return 0;

}