• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

原题链接:

洛古模板问题

题目:

例如,给定一个序列,你需要做以下两个操作:

1.一定区间内的每个数字加K。

2.求某区间内各数之和。输入格式:

第一行包含两个整数n,m,分别代表序列中数字的个数和运算总数。

第二行包含由空格分隔的n个整数,其中第I个数字表示序列中第I项的初始值。

接下来的M行各包含3或4个整数,代表一个操作,如下所示:

1 x y k表示将k加到区间[x,y]中的所有数上。

X y表示查询[x,y]区间中的总输出格式:

输出包含几行整数,这是所有操作2的结果。输入 #1

5 5

1 5 4 2 3

2 2 4

1 2 3 2

2 3 4

1 1 5 1

214输出 #1

11

20说明:

所有数据范围:1 n,m 1e5

答案是长远的。

思路:

这个题目是“用段树应该写什么?”是因为修改了区间,查询了区间。如果被修改,单点查询、

用树阵不好闻吗?那么段树的区间修改就涉及到懒标记的使用。

段树的区间运算可以使用惰性标记来优化时间复杂度,具体实现还得写一个下推函数,用来

懒值传给他的儿子,这样查询前的N步就可以变成一步,大大优化了时间复杂度,具体实现。

并不复杂,重要的是多练习(我还是太擅长做菜了)。

#includebits/stdc。h

使用命名空间std

#define endl '\n '

#定义int long long

typedef pairint,int PII;

const int mod=1e 9 7;

const int INF=0x 3 F3 F3 f 3 f;

const int N=1e5 10

int n,m;

int w[N];

结构节点{

int l,r;

int sum,add

} tr[N ^ 2];

void pushup(int u){

trsum=tr[u 1]。总和tr[u 1 | 1]。总和;

}

下推操作中Void pushdown (int u) {//sum=x。我开始写=,花了很长时间去改变一切。我很难过。

if(tr)。添加){

tr[u 1]。sum=(tr[u 1]。r - tr[u 1]。l 1) * tr。添加;

tr[u 1 | 1]。sum=(tr[u 1 | 1]。r - tr[u 1 | 1]。l 1) * tr。添加;

tr[u 1]。add=tr。添加;

tr[u 1 | 1]。add=tr。添加;

tradd=0;

}

}

void build(int u,int l,int r){

trl=l,tr。r=r

if(l==r) tr。sum=w[l];

否则{

int mid=l r 1;

build(u 1,l,mid);build(u 1 | 1,mid 1,r);

俯卧撑(u);

}

}

Voidmodify (int u,int l,int r,int k){//包含在指定的区间内,然后进行运算。如果包含的操作符写清楚了,就不会调试这么久了。

if(tr)。l=l tr。r=r){

trsum=(tr)。r - tr。l 1)* k;

tradd=k;

}

否则{

下推(u);

int mid=tr。l tr。R1;

if(l=mid)修改(u 1,l,r,k);

if(r mid) modify(u 1 | 1,l,r,k);

俯卧撑(u);

}

}

int query(int u,int l,int r){

if(tr)。l=l tr。r=r){

//cout tr。l ' ' tr。r endl

return tr。总和;

}

否则{

下推(u);

int mid=tr。l tr。R1;

int RES=0;

if(l=mid) res=query(u 1,l,r);

if(r mid) res=query(u 1 | 1,l,r);

返回res

}

}

签名主(无效){

IOs : sync _ with _ stdio(false);

CIN . tie(0);

CIN nm;

for(int I=1;I=n;我)

CIN w

build(1,1,n);

for(int I=1;I=m;i ){

int op,l,r,k;

CIN op l r;

if(op==1){

CIN k;

modify(1,l,r,k);

}

否则{

cout query(1,l,r)endl;

}

}

返回0;

}

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now