线段树 - 维护序列

维护序列 总时间限制: 30000ms 单个测试点时间限制: 3000ms 内存限制: 128000kB

描述 老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 　　有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式： 　　(1)把数列中的一段数全部乘一个值; 　　(2)把数列中的一段数全部加一个值; 　　(3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。

输入 第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作1：“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。 操作2：“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3：“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值(1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。 　　 输出 对每个操作3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

样例输入 7 43 1 2 3 4 5 6 7 5 1 2 5 5 3 2 4 2 3 7 9 3 1 3 3 4 7

样例输出 2 35 8

样例说明 　　初始时数列为(1,2,3,4,5,6,7)。 　　经过第1次操作后，数列为(1,10,15,20,25,6,7)。 　　对第2次操作，和为10+15+20=45，模43的结果是2。 　　经过第3次操作后，数列为(1,10,24,29,34,15,16} 　　对第4次操作，和为1+10+24=35，模43的结果是35。 　　对第5次操作，和为29+34+15+16=94,模43的结果是8。

数据规模和约定 　　测试数据规模如下表所示: 数据编号 1 2 3 4 5 6 7 8 9 10 N= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000 M= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000

来源 AHOI2009

这道题一来就知道要用线段树，而且是区间修改的那种。与之前的线段树不同的是，这道题有两种操作，一是乘法，二是加法。这就让某些具体实现发生了变化，让我们还是从区间线段树的原理出发，来看看这道题怎么做。 首先，毋庸置疑的是树的大小和建树的方法同普通的线段树仍然没有差别。由于数据规模是100000，所以树至少要2^ceil(log2(100000))+1 这么大，这里我取262150：

const int maxn=262150; long long tree[maxn];

为什么要用long long？因为操作的数实在是太大，太大了，稍不注意就会溢出，所以不如用long long一劳永逸。

建树时要使用递归输入，因为这样就可以省下一个大大的原始数据数组：

void build(int node=1, int l=1, int r=n) { if(l==r) { tree[node]=readIn()%mod; return; } int mid=(l+r)/2; build(node<<1, l, mid); build((node<<1)+1, mid+1, r); tree[node]=(tree[node<<1]+tree[(node<<1)+1])%mod; }

readIn()函数不仅是为了方便，而且是为输入的安全。readIn就是我写的是用 scanf 输入long long的代码，如果要保存到一个int类型的数据里，可以使用类型转换，这样有效避免了scanf错误地写内存。 为什么不用cin？线段树类型的问题需要输入大量的数据，使用cin是会超时的。

区间线段树最关键的地方还是那个用于节省大量时间的 lazy 操作。由于本题有两种操作，因此我干脆定义一个结构体：

struct handle { long long mul; long long add; handle():mul(1),add(0) { } } lazy[maxn];

使用long long的理由同上。初始值分别设为0或1是为了操作的方便，这样就不用加一个额外标记（比如-1）来判断是否有怠惰标记了（这样会让代码至少少个20行）。

如果不使用怠惰标记，剩下的就无话可说了，就是普通的线段树。有了怠惰标记，我们就要首先考虑那个pushDown操作。让我们来回忆一下pushDown操作的通用写法。 首先，看一下一般的pushDown的函数原型：

void pushDown(int node, int l, int r); //node,l,r都在调用时传入，没什么好说的

在一开始，一般来说还需要判断是否有标记，像这样：

void pushDown(int node, int l, int r) { if(lazy[node].mul != -1) //如果有标记 { //... 把子结点的线段树和lazy更新 lazy[node].mul = -1; //传下去了，清除标记 } }

由于之前我们处理过lazy结构，在不修改lazy结构的情况下pushDown操作不会引起数据的改变（乘以1，加上0，当然不会），所以这里就可以免了。

考虑一下乘法和加法操作的顺序。如果我们先后进行了乘法和加法，那么lazy操作只需要先把tree 乘以 mul，再把tree 加上 add * (mid - l + 1) （注意不是只加上add！！！），最后让子结点的lazy.mul 乘以 mul，lazy.add 加上 add 就可以了，一切都是那么和谐。但是！如果先执行加法，后执行乘法，那么lazy操作就需要先把tree 加上 add * (mid - l + 1)，再把tree 乘以 mul。注意！是不是可以发现add * (mid - l + 1)也被乘以了mul了呢？所以对子结点的lazy结构的操作就有点变化了。先让lazy.add 加上 add * (mid - l + 1)，再让lazy.mul 乘以 mul，最后还要让lazy.add 乘上一个 mul。 考虑之前我们对lazy结构的初始化，我们可以把这两个情况合并：

void pushDown(int node, int l, int r) { int lc=node<<1; int rc=(node<<1)+1; int mid=(l+r)/2; tree[lc] = tree[lc] * lazy[node].mul % mod; tree[lc] = (tree[lc] + lazy[node].add * (mid-l+1) % mod) % mod; tree[rc] = tree[rc] * lazy[node].mul % mod; //刚刚是以左子树举例，不要漏了右子树 tree[rc] = (tree[rc] + lazy[node].add * (r-mid) % mod) % mod; lazy[lc].mul=lazy[lc].mul * lazy[node].mul % mod; lazy[lc].add=lazy[lc].add * lazy[node].mul % mod; lazy[lc].add=(lazy[lc].add + lazy[node].add % mod) % mod; lazy[rc].mul=lazy[rc].mul * lazy[node].mul % mod; lazy[rc].add=lazy[rc].add * lazy[node].mul % mod; lazy[rc].add=(lazy[rc].add + lazy[node].add % mod) % mod; lazy[node].add = 0; lazy[node].mul = 1; //回归初始状态 }

有了pushDown，add和mul写起来就好写多了：

void add(int node=1, int l=1, int r=n) { if(g_L<=l && r<=g_R) { tree[node]=(tree[node] + g_Var * (r-l+1) % mod) % mod; //记住乘上(r-l+1) lazy[node].add = (lazy[node].add + g_Var) % mod; //记住更新lazy结构 return; } pushDown(node, l, r); int lc=node<<1; int rc=(node<<1)+1; int mid=(l+r)/2; if(g_L <= mid) add(lc, l, mid); //记住加上条件 if(g_R > mid) add(rc, mid+1, r); tree[node]=(tree[lc]+tree[rc])%mod; //记住计算完了要回来更新父结点 } void mul(int node=1, int l=1, int r=n) { if(g_L<=l && r<=g_R) { tree[node]=tree[node] * g_Var % mod; lazy[node].mul = lazy[node].mul * g_Var % mod; lazy[node].add = lazy[node].add * g_Var % mod; //注意！！！ return; } pushDown(node, l, r); int lc=node<<1; int rc=(node<<1)+1; int mid=(l+r)/2; if(g_L <= mid) mul(lc, l, mid); if(g_R > mid) mul(rc, mid+1, r); tree[node]=(tree[lc]+tree[rc])%mod; }

正如前文所说，进行乘法操作时要记住把加法的标记也乘上指定的数。

最后是sum操作。没什么好说的了，看参考代码吧，记住每次都要pushDown。

参考代码

#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <deque> #include <map> #include <set> using std::cin; using std::cout; using std::endl; inline long long readIn() { long long a; scanf("%lld",&a); return a; } const int maxn=262150; int n,m; int mod; long long tree[maxn]; struct handle { long long mul; long long add; handle():mul(1),add(0) { } } lazy[maxn]; namespace Regular { void build(int node=1, int l=1, int r=n) { if(l==r) { tree[node]=readIn()%mod; return; } int mid=(l+r)/2; build(node<<1, l, mid); build((node<<1)+1, mid+1, r); tree[node]=(tree[node<<1]+tree[(node<<1)+1])%mod; } int g_L,g_R,g_Var; void pushDown(int node, int l, int r) { int lc=node<<1; int rc=(node<<1)+1; int mid=(l+r)/2; tree[lc] = tree[lc] * lazy[node].mul % mod; tree[lc] = (tree[lc] + lazy[node].add * (mid-l+1) % mod) % mod; tree[rc] = tree[rc] * lazy[node].mul % mod; tree[rc] = (tree[rc] + lazy[node].add * (r-mid) % mod) % mod; lazy[lc].mul=lazy[lc].mul * lazy[node].mul % mod; lazy[lc].add=lazy[lc].add * lazy[node].mul % mod; lazy[lc].add=(lazy[lc].add + lazy[node].add % mod) % mod; lazy[rc].mul=lazy[rc].mul * lazy[node].mul % mod; lazy[rc].add=lazy[rc].add * lazy[node].mul % mod; lazy[rc].add=(lazy[rc].add + lazy[node].add % mod) % mod; lazy[node].add = 0; lazy[node].mul = 1; } int sum(int node=1, int l=1, int r=n) { if(g_L<=l && r<=g_R) { return tree[node] % mod; } pushDown(node, l, r); int lc=node<<1; int rc=(node<<1)+1; int mid=(l+r)/2; long long ans=0; if(g_L <= mid) ans+=sum(lc, l, mid); if(g_R > mid) ans+=sum(rc, mid+1, r); return ans % mod; } void add(int node=1, int l=1, int r=n) { if(g_L<=l && r<=g_R) { tree[node]=(tree[node] + g_Var * (r-l+1) % mod) % mod; lazy[node].add = (lazy[node].add + g_Var) % mod; return; } pushDown(node, l, r); int lc=node<<1; int rc=(node<<1)+1; int mid=(l+r)/2; if(g_L <= mid) add(lc, l, mid); if(g_R > mid) add(rc, mid+1, r); tree[node]=(tree[lc]+tree[rc])%mod; } void mul(int node=1, int l=1, int r=n) { if(g_L<=l && r<=g_R) { tree[node]=tree[node] * g_Var % mod; lazy[node].mul = lazy[node].mul * g_Var % mod; lazy[node].add = lazy[node].add * g_Var % mod; return; } pushDown(node, l, r); int lc=node<<1; int rc=(node<<1)+1; int mid=(l+r)/2; if(g_L <= mid) mul(lc, l, mid); if(g_R > mid) mul(rc, mid+1, r); tree[node]=(tree[lc]+tree[rc])%mod; } enum { MUL=1, ADD, SUM }; void run() { while(m--) { int ins=readIn(); if(ins==MUL) { g_L=readIn(); g_R=readIn(); g_Var=readIn() % mod; mul(); } else if(ins==ADD) { g_L=readIn(); g_R=readIn(); g_Var=readIn() % mod; add(); } else if(ins==SUM) { g_L=readIn(); g_R=readIn(); printf("%d\n",sum()); } } } void input() { n=readIn(); mod=readIn(); build(); m=readIn(); } } namespace Violent { void run() { } void input() { } } int main() { Regular::input(); Regular::run(); return 0; }

先前把一个地方的 g_ Var写成了 g_ R，结果一分没得（暴力都得了40分）。改了代码后得了60分，最后把int改成long long后就通过了。虽然long long可能在输入输出上有些不保险，但是相比溢出带来的问题，都不算什么，只要不乱写代码、仔细一点，就没有问题了。