强行刷线段树

我这种菜鸡怎么会自己手打线段树，自从上海邀请赛被虐，多校第二场被肝，线段树就成了头悬之剑

题目地址 

http://acm.hdu.edu.cn/showproblem.php?pid=5634

Rikka with Phi

 
Rikka and Yuta are interested in Phi function (which is known as Euler's totient function). 

Yuta gives Rikka an array A[1..n]A[1..n] of positive integers, then Yuta makes mm queries. 

There are three types of queries: 

1lr1lr 

Change A[i]A[i] into φ(A[i])φ(A[i]), for all i∈[l,r]i∈[l,r]. 

2lrx2lrx 

Change A[i]A[i] into xx, for all i∈[l,r]i∈[l,r]. 

3lr3lr 

Sum up A[i]A[i], for all i∈[l,r]i∈[l,r]. 

Help Rikka by computing the results of queries of type 3. 

InputThe first line contains a number T(T≤100)T(T≤100) ——The number of the testcases. And there are no more than 2 testcases with n>105n>105 

For each testcase, the first line contains two numbers n,m(n≤3×105,m≤3×105)n,m(n≤3×105,m≤3×105)。 

The second line contains nn numbers A[i]A[i] 

Each of the next mm lines contains the description of the query. 

It is guaranteed that 1≤A[i]≤1071≤A[i]≤107 At any moment.OutputFor each query of type 3, print one number which represents the answer.Sample Input 
1
10 10
56 90 33 70 91 69 41 22 77 45
1 3 9
1 1 10
3 3 8
2 5 6 74
1 1 8
3 1 9
1 2 10
1 4 9
2 8 8 69
3 3 9
Sample Output 
80
122
86
把欧拉函数也扔进去暴力更新
#include<stdio.h>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
const int N=3e5+5,M=1e7+5;
ll lazy[N<<2],sum[N<<2];
int n,m,a[N];
ll euler[M];
void Euler()
{
    for(int i=1; i<M; i++)euler[i]=i;
    for(int i=2; i<M; i++)
        if(euler[i]==i)
            for(int j=i; j<M; j+=i)euler[j]=euler[j]/i*(i-1);
}
void PushUp(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    lazy[rt]=(lazy[rt<<1]==lazy[rt<<1|1])?lazy[rt<<1]:0;
}
void PushDown(int rt,int len)
{
    if(!lazy[rt])return;
    lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
    sum[rt<<1]=lazy[rt]*(len-(len>>1)),sum[rt<<1|1]=lazy[rt]*(len>>1);
    lazy[rt]=0;
}
void Build(int l,int r,int rt)
{
    sum[rt]=lazy[rt]=0;
    if(l==r)
    {
        int x;
        scanf("%d",&x);
        sum[rt]=lazy[rt]=x;
        return;
    }
    int mid=(l+r)>>1;
    Build(lson),Build(rson);
    PushUp(rt);
}
void Modify(int L,int R,int c,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        lazy[rt]=c,sum[rt]=(r-l+1)*1LL*c;
        return;
    }
    PushDown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid)Modify(L,R,c,lson);
    if(R>mid)Modify(L,R,c,rson);
    PushUp(rt);
}
void Eu(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R&&lazy[rt])
    {
        lazy[rt]=euler[lazy[rt]],sum[rt]=lazy[rt]*(r-l+1);
        return;
    }
    if(l==r)return;
    PushDown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid)Eu(L,R,lson);
    if(R>mid)Eu(L,R,rson);
    PushUp(rt);
}
ll Sum(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)return sum[rt];
    PushDown(rt,r-l+1);
    int mid=(l+r)>>1;
    ll ans=0;
    if(L<=mid)ans+=Sum(L,R,lson);
    if(R>mid)ans+=Sum(L,R,rson);
    PushUp(rt);
    return ans;
}
int main()
{
    Euler();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        Build(1,n,1);
        while(m--)
        {
            int op,x,y,z;
            scanf("%d%d%d",&op,&x,&y);
            switch(op)
            {
            case 2:
                scanf("%d",&z),Modify(x,y,z,1,n,1);
                break;
            case 1:
                Eu(x,y,1,n,1);
                break;
            case 3:
                printf("%lld
",Sum(x,y,1,n,1));
            }
        }
    }
    return 0;
}

Naive Operations

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 502768/502768 K (Java/Others)
Total Submission(s): 2556    Accepted Submission(s): 1123


Problem Description
In a galaxy far, far away, there are two integer sequence a and b of length n.
b is a static permutation of 1 to n. Initially a is filled with zeroes.
There are two kind of operations:
1. add l r: add one for al,al+1...ar
2. query l r: query ∑ri=l⌊ai/bi⌋
 
Input
There are multiple test cases, please read till the end of input file.
For each test case, in the first line, two integers n,q, representing the length of a,b and the number of queries.
In the second line, n integers separated by spaces, representing permutation b.
In the following q lines, each line is either in the form 'add l r' or 'query l r', representing an operation.
1≤n,q≤100000, 1≤l≤r≤n, there're no more than 5 test cases.
 
Output
Output the answer for each 'query', each one line.
 
Sample Input
5 12
1 5 2 4 3
add 1 4
query 1 4
add 2 5
query 2 5
add 3 5
query 1 5
add 2 4
query 1 4
add 2 5
query 2 5
add 2 2
query 1 5
 
Sample Output
1
1
2
4
4
6
 
Source
2018 Multi-University Training Contest 2

 怎么可能是数学题，这个就是/全排列，但是每一个又不一样，只能暴力更新

所以区间除法就转换为区间减法，减到0时重新赋值，维护最小值，暴力更新就好了

#include<stdio.h>
#include<algorithm>
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
const int N=1e5+5;
int a[N<<2],lazy[N<<2],b[N],sum[N<<2];
int n;
void PushUp(int rt)
{
    a[rt]=std::min(a[rt<<1],a[rt<<1|1]),sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void PushDown(int rt)
{
    if(lazy[rt]==0)return;
    lazy[rt<<1]+=lazy[rt],lazy[rt<<1|1]+=lazy[rt];
    a[rt<<1]-=lazy[rt],a[rt<<1|1]-=lazy[rt];
    lazy[rt]=0;
}
void Build(int l,int r,int rt)
{
    lazy[rt]=0,sum[rt]=0;
    if(l==r)
    {
        scanf("%d",&b[l]),a[rt]=b[l];
        return;
    }
    Build(lson),Build(rson);
    PushUp(rt);
}
void Update(int L,int R,int l,int r,int rt)
{
    if(a[rt]>1&&L<=l&&r<=R)
    {
        lazy[rt]++,a[rt]--;
        return;
    }
    if(l==r&&a[rt]==1)
    {
        sum[rt]++,lazy[rt]=0,a[rt]=b[l];
        return;
    }
    int mid=(l+r)>>1;
    PushDown(rt);
    if(L<=mid)Update(L,R,lson);
    if(R>mid)Update(L,R,rson);
    PushUp(rt);
}
int Query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)return sum[rt];
    if(a[rt]<=0)Update(L,R,1,n,1);
    int mid=(l+r)>>1,ans=0;
    PushDown(rt);
    if(L<=mid)ans+=Query(L,R,lson);
    if(R>mid)ans+=Query(L,R,rson);
    PushUp(rt);
    return ans;
}
int main()
{
    int q;
    char op[10];
    while(~scanf("%d%d",&n,&q))
    {
        Build(1,n,1);
        for(int i=0,x,y; i<q; i++)
        {
            scanf("%s%d%d",op,&x,&y);
            if(op[0]=='a')
                Update(x,y,1,n,1);
            else
                printf("%d
",Query(x,y,1,n,1));
        }
    }
    return 0;
}

#6029. 「雅礼集训 2017 Day1」市场

题目描述

从前有一个贸易市场，在一位执政官到来之前都是非常繁荣的，自从他来了之后，发布了一系列奇怪的政令，导致贸易市场的衰落。

有 n nn 个商贩，从 0∼n−1 0 sim n - 10∼n−1 编号，每个商贩的商品有一个价格 ai a_ia​i​​，有两种政令：

  1. l,r,c l, r, cl,r,c，对于 i∈[l,r],ai←ai+c i in [l, r], a_i leftarrow a_i + ci∈[l,r],a​i​​←a​i​​+c
  2. l,r,d l, r, dl,r,d，对于 i∈[l,r],ai←⌊ai/d⌋ i in [l, r], a_i leftarrow lfloor {a_i}/{d} floori∈[l,r],a​i​​←⌊a​i​​/d⌋

现在有一个外乡的旅客想要了解贸易市场的信息，有两种询问方式：

  1. 给定 l,r l, rl,r，求 mini∈[l,r]ai min_{i in [l, r]} a_imin​i∈[l,r]​​a​i​​
  2. 给定 l,r l, rl,r，求 ∑i∈[l,r]ai sum_{iin [l, r]} a_i∑​i∈[l,r]​​a​i​​

输入格式

第一行为两个空格隔开的整数 n,q n, qn,q 分别表示商贩个数和政令 + 询问个数。
第二行包含 n nn 个由空格隔开的整数 a0∼an−1 a_0 sim a_{n - 1}a​0​​∼a​n−1​​
接下来 q qq 行，每行表示一个操作，第一个数表示操作编号 1∼4 1 sim 41∼4，接下来的输入和问题描述一致。

输出格式

对于每个 3、4 操作，输出询问答案。

样例

样例输入

10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9

样例输出

-2
-2
-2
-2
0
1
1

数据范围与提示

对于 30% 30\%30% 的数据，n,q≤103 n, q leq 10 ^ 3n,q≤10​3​​；
对于 60% 60\%60% 的数据，保证数据随机；
对于 100% 100\%100% 的数据，1≤n,q≤105,0≤l≤r≤n−1,c∈[−104,104],d∈[2,109] 1 leq n, q leq 10 ^ 5, 0 leq l leq r leq n - 1, c in [-10 ^ {4}, 10 ^ 4], d in [2, 10 ^ 9]1≤n,q≤10​5​​,0≤l≤r≤n−1,c∈[−10​4​​,10​4​​],d∈[2,10​9​​]

区间加法，区间减法，但是不能暴力更新，因为除的数不确定
经过枚举和看别人博客可以发现是和最大最小值有关的，然后打上lazy就好了
#include<stdio.h>
#include<algorithm>
#include<iostream>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
const int N=1e5+5;
ll lazy[N<<2],sum[N<<2],Max[N<<2],Min[N<<2];
int n,m,a[N];
void PushUp(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    Max[rt]=std::max(Max[rt<<1],Max[rt<<1|1]),Min[rt]=std::min(Min[rt<<1],Min[rt<<1|1]);
}
void PushDown(int rt,int len)
{
    if(!lazy[rt])return;
    lazy[rt<<1]+=lazy[rt],lazy[rt<<1|1]+=lazy[rt];
    sum[rt<<1]+=lazy[rt]*(len-(len>>1)),sum[rt<<1|1]+=lazy[rt]*(len>>1);
    Max[rt<<1]+=lazy[rt],Max[rt<<1|1]+=lazy[rt];
    Min[rt<<1]+=lazy[rt],Min[rt<<1|1]+=lazy[rt];
    lazy[rt]=0;
}
void Build(int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]=Max[rt]=Min[rt]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    Build(lson),Build(rson);
    PushUp(rt);
}
void Modify(int L,int R,int c,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        lazy[rt]+=c,sum[rt]+=(r-l+1)*1LL*c,Max[rt]+=c,Min[rt]+=c;
        return;
    }
    PushDown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid)Modify(L,R,c,lson);
    if(R>mid)Modify(L,R,c,rson);
    PushUp(rt);
}
void Div(int L,int R,int c,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        ll X=(Min[rt]>=0)?Min[rt]/c:(Min[rt]-c+1)/c,Y=(Max[rt]>=0)?Max[rt]/c:(Max[rt]-c+1)/c;
        //std::cout<<Min[rt]<<" "<<X<<" "<<Max[rt]<<" "<<Y<<"
";
        if(X-Min[rt]==Y-Max[rt])
        {
            lazy[rt]+=X-Min[rt],sum[rt]+=(X-Min[rt])*(r-l+1),Max[rt]+=X-Min[rt],Min[rt]+=X-Min[rt];
            return;
        }
    }
    PushDown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid)Div(L,R,c,lson);
    if(R>mid)Div(L,R,c,rson);
    PushUp(rt);
}
ll Sum(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)return sum[rt];
    PushDown(rt,r-l+1);
    int mid=(l+r)>>1;
    ll ans=0;
    if(L<=mid)ans+=Sum(L,R,lson);
    if(R>mid)ans+=Sum(L,R,rson);
    return ans;
}
ll QMin(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)return Min[rt];
    PushDown(rt,r-l+1);
    int mid=(l+r)>>1;
    ll ans=1e18;
    if(L<=mid)ans=std::min(ans,QMin(L,R,lson));
    if(R>mid)ans=std::min(ans,QMin(L,R,rson));
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)scanf("%d",&a[i]);
    Build(1,n,1);
    //for(int i=1; i<=n; i++)printf("%d
",sum[i]);
    while(m--)
    {
        int op,x,y,z;
        scanf("%d%d%d",&op,&x,&y),x++,y++;
        switch(op)
        {
            case 1:scanf("%d",&z),Modify(x,y,z,1,n,1);break;
            case 2:scanf("%d",&z),Div(x,y,z,1,n,1);break;
            case 3:printf("%lld
",QMin(x,y,1,n,1));break;
            case 4:printf("%lld
",Sum(x,y,1,n,1));
        }
    }
    return 0;
}

#228. 基础数据结构练习题

sylvia 是一个热爱学习的女孩子，今天她想要学习数据结构技巧。

在看了一些博客学了一些姿势后，她想要找一些数据结构题来练练手。于是她的好朋友九条可怜酱给她出了一道题。

给出一个长度为 nn 的数列 AA，接下来有 mm 次操作，操作有三种：

  1. 对于所有的 i∈[l,r]i∈[l,r]，将 AiAi 变成 Ai+xAi+x。
  2. 对于所有的 i∈[l,r]i∈[l,r]，将 AiAi 变成 ⌊Ai−−√⌋⌊Ai⌋。
  3. 对于所有的 i∈[l,r]i∈[l,r]，询问 AiAi 的和。

作为一个不怎么熟练的初学者，sylvia 想了好久都没做出来。而可怜酱又外出旅游去了，一时间联系不上。于是她决定向你寻求帮助：你能帮她解决这个问题吗。

输入格式

第一行两个数：n,mn,m。

接下来一行 nn 个数 AiAi。

接下来 mm 行中，第 ii 行第一个数 titi 表示操作类型：

若 ti=1ti=1，则接下来三个整数 li,ri,xili,ri,xi，表示操作一。

若 ti=2ti=2，则接下来三个整数 li,rili,ri，表示操作二。

若 ti=3ti=3，则接下来三个整数 li,rili,ri，表示操作三。

输出格式

对于每个询问操作，输出一行表示答案。

样例一

input

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

output

5
6

样例二

见样例数据下载。

限制与约定

测试点编号nn 的规模mm 的规模其他约定
1 n≤3000n≤3000 m≤3000m≤3000  
2
3
4 n≤100000n≤100000 m≤100000m≤100000 数据随机生成
5
6 ti≠1ti≠1
7
8  
9
10

对于所有数据，保证有 1≤li≤ri≤n,1≤Ai,xi≤1051≤li≤ri≤n,1≤Ai,xi≤105

时间限制：1s1s

空间限制：256MB

这个题目就更有意思了，区间开根号，但是同一个世界，同一个梦想，区间开根号这个更新很快的

#include<stdio.h>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
const int N=1e5+5;
ll lazy[N<<2],sum[N<<2],Max[N<<2],Min[N<<2];
int n,m,a[N];
void PushUp(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    Max[rt]=std::max(Max[rt<<1],Max[rt<<1|1]),Min[rt]=std::min(Min[rt<<1],Min[rt<<1|1]);
}
void PushDown(int rt,int len)
{
    if(!lazy[rt])return;
    lazy[rt<<1]+=lazy[rt],lazy[rt<<1|1]+=lazy[rt];
    sum[rt<<1]+=lazy[rt]*(len-(len>>1)),sum[rt<<1|1]+=lazy[rt]*(len>>1);
    Max[rt<<1]+=lazy[rt],Max[rt<<1|1]+=lazy[rt];
    Min[rt<<1]+=lazy[rt],Min[rt<<1|1]+=lazy[rt];
    lazy[rt]=0;
}
void Build(int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]=Max[rt]=Min[rt]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    Build(lson),Build(rson);
    PushUp(rt);
}
void Modify(int L,int R,int c,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        lazy[rt]+=c,sum[rt]+=(r-l+1)*1LL*c,Max[rt]+=c,Min[rt]+=c;
        return;
    }
    PushDown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid)Modify(L,R,c,lson);
    if(R>mid)Modify(L,R,c,rson);
    PushUp(rt);
}
void Sqrt(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        if(Max[rt]-Min[rt]==(ll)sqrt(Max[rt])-(ll)sqrt(Min[rt])||Max[rt]==Min[rt])
        {
            ll z=(ll)sqrt(Max[rt])-Max[rt];
            sum[rt]+=z*(r-l+1),Max[rt]+=z,Min[rt]+=z,lazy[rt]+=z;
            return;
        }
    }
    PushDown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid)Sqrt(L,R,lson);
    if(R>mid)Sqrt(L,R,rson);
    PushUp(rt);
}
ll Sum(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)return sum[rt];
    PushDown(rt,r-l+1);
    int mid=(l+r)>>1;
    ll ans=0;
    if(L<=mid)ans+=Sum(L,R,lson);
    if(R>mid)ans+=Sum(L,R,rson);
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)scanf("%d",&a[i]);
    Build(1,n,1);
    //for(int i=1; i<=n; i++)printf("%d
",sum[i]);
    while(m--)
    {
        int op,x,y,z;
        scanf("%d%d%d",&op,&x,&y);
        switch(op)
        {
            case 1:scanf("%d",&z),Modify(x,y,z,1,n,1);break;
            case 2:Sqrt(x,y,1,n,1);break;
            case 3:printf("%lld
",Sum(x,y,1,n,1));
        }
    }
    return 0;
}

4399: Deal with numbers 分享至QQ空间

Time Limit(Common/Java):10000MS/30000MS     Memory Limit:65536KByte
Total Submit: 26            Accepted:7

Description

 

There are n numbers with the corresponding NO.1-n, and the value of the i-th number is xi.

Define three operations:

    1.Division a b c, in the interval [a,b], if the value of a number is equal or greater than zero, then its value changed to it divide C(integer division). (1 <= a <= b <= n, 1 <= c <= 50000)

    2.Minus a b c, all numbers in the interval [a, b] subtract c. (1 <= a <= b <= n ,1<= c <= 50000)

    3.Sum a b, query for the sum of all numbers in the interval [a, b]. (1 <= a <= b <= n)

Input

 

Input contains several test cases.

The first line is an integer T indicates the number of test cases.

For each test case, the first line contains two integer numbers n and m (1<=n,m<=10^5), indicates the number of numbers and the number of operations. The second line contains n integers, the i-th integer shows the original value of the i-th number (1<=xi<=50000). Then m lines followed, each line shows an operation.

Output

 

For each set of data, output the case number in a line first, and then for each query, output an integer in a line to show the answer.

Print a blank line after the end of each test cases.
 

Sample Input

 

2
5 5
1 2 3 4 5
Division 1 3 2
Minus 3 5 3
Sum 1 2
Sum 3 4
Sum 5 5
5 3
-2 -1 3 -2 1
Sum 1 2
Division 1 2 2
Sum 1 2

Sample Output

 

Case 1:
1
-1
2

Case 2:
-3
-3

whu的题目。但是咕咕咕了啊，在他们新OJ时间只有1s，TLE on test1

#include<stdio.h>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
const int N=1e5+5;
ll add[N<<2],sum[N<<2];
bool flag[N<<2];
void PushUp(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1],flag[rt]=flag[rt<<1]|flag[rt<<1|1];
}
void PushDown(int rt,int len)
{
    if(!add[rt])return;
    add[rt<<1]+=add[rt],add[rt<<1|1]+=add[rt];
    sum[rt<<1]+=add[rt]*(len-(len>>1)),sum[rt<<1|1]+=add[rt]*(len>>1);
    add[rt]=0;
}
void Build(int l,int r,int rt)
{
    add[rt]=sum[rt]=0;
    if(l==r)
    {
        scanf("%I64d",&sum[rt]),flag[rt]=(sum[rt]>0);
        return;
    }
    int mid=(l+r)>>1;
    Build(lson),Build(rson);
    PushUp(rt);
}
void Minus(int L,int R,int c,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        add[rt]+=c,sum[rt]+=(r-l+1)*c;
        return;
    }
    PushDown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid)Minus(L,R,c,lson);
    if(R>mid)Minus(L,R,c,rson);
    PushUp(rt);
}
void Division(int L,int R,int c,int l,int r,int rt)
{
    if(!flag[rt])return;
    if(l==r)
    {
        if(sum[rt]>0)sum[rt]/=(ll)c;
        flag[rt]=(sum[rt]>0);
        return;
    }
    PushDown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid)Division(L,R,c,lson);
    if(R>mid)Division(L,R,c,rson);
    PushUp(rt);
}
ll Sum(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)return sum[rt];
    PushDown(rt,r-l+1);
    int mid=(l+r)>>1;
    ll ans=0;
    if(L<=mid)ans+=Sum(L,R,lson);
    if(R>mid)ans+=Sum(L,R,rson);
    return ans;
}
int main()
{
    int T,ca=0;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        char op[10];
        scanf("%d%d",&n,&m);
        printf("Case %d:
",++ca);
        Build(1,n,1);
        for(int i=0,a,b,c; i<m; i++)
        {
            scanf("%s",op);
            if(op[0]=='D')
            {
                scanf("%d%d%d",&a,&b,&c);
                if(c!=1)Division(a,b,c,1,n,1);
            }
            else if(op[0]=='M')
            {
                scanf("%d%d%d",&a,&b,&c);
                if(c)Minus(a,b,-c,1,n,1);
            }
            else
                scanf("%d%d",&a,&b),printf("%I64d
",Sum(a,b,1,n,1));
        }
        putchar(10);
    }
    return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/BobHuang/p/9388960.html