NewCoder The Trip On Abandoned Railway

发表于 | 分类于 | ℃热度
~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

The Trip On Abandoned Railway

题面

There are many ghosts at the abandoned station on unknown railway.

We mark the abandoned stations as $1,2..n$ according to the order. There are $a_i$ ghosts at the $i^{th}$ station.Yakumo Yukari often opens a black hole and makes a train appearing at a certain station. For example, the train appears at the $x$ station, and $k$ ghosts get off at the station. Then there would be $k+d$ ghosts at the $x+1$ station to get off,$k+2×d$ at $x+2$ station and so on….There would be $k+y∗d$ ghosts at the $x+y$ station to get off ($0≤y,x+y≤n$). In others words, the numbers getting off at $x,x+1,x+2..n$ station form a tolerance of $d$ arithmetic progression.(you can consider ghosts getting off at the same time.)Onozuka Komachi would comes a certain station to take away the ghosts.(The number of ghosts at the station would become $0$)You have the records of trains appearing and Komachi coming. You should tell Komachi how much ghosts at a certain station when she come to there.

简要翻译

一开始给定一个序列$a_i$，你要进行两种操作。

  1. 从第$x$个位置到第$n$个位置，分别加上$y,y+d,y+2×d,y+3×d…$的一个等差数列。
  2. 询问第$x$个位置的数，并且将该位置清零。
Input

第一行包含一个整数$T$，表示测试数据的组数。

每组数据第一行包含三个整数$n$,$m$,$d$，其中$n$表示序列长度，$m$表示操作个数，$d$表示等差数列的公差。第二行包含$n$个整数，表示$a_i$。下面包含$m$行，每行开头一个整数$1/2$，表示操作类型。

  1. 如果是$1$，则下面有两个整数$x$,$y$如题意。
  2. 如果是$2$，则下面包含一个整数$x$表示要查询的位置。
Output

对于每个$2$操作，输出一个整数表示答案。

Sample Input

2
6 6 1
1 2 3 3 2 1
1 1 1
2 1
2 2
2 3
2 4
2 5
5 3 2
1 2 3 4 5
1 3 0
2 4
2 4

Simple Output

2
4
6
7
7
6
0

Hint

$1\le T\le 10$。

$1\le n\le 10^5$，$1\le m\le 10^5$，$1\le d\le 10^3$。

$1\le a_i\le 10^3$，$1\le x\le n$，$0\le y\le 10^3$。

样例说明

说明每一次操作后的序列：

1
2
3
4
5
6
7
8
case1：
1 2 3 3 2 1
2 4 6 7 7 7
0 4 6 7 7 7
0 0 6 7 7 7
0 0 0 7 7 7
0 0 0 0 7 7
0 0 0 0 0 7
1
2
3
4
5
case2：
1 2 3 4 5
1 2 3 6 9
1 2 3 0 9
1 2 3 0 9

emmmmm，之前做过一道题，所以这题切起来比较轻松。

加上等差数列，我们明显就可以知道，等差数列每一项之差就是$d$，所以我们只要将$x+1$~$n$的位置都加上$d$，用线段树修改区间，在$x$的位置上用树状数组单点修改。查询时，求出线段树上$x$的前缀表示修改的总和，加上树状数组$x$位置的值和原本该位置上的值，求和即可。对于清空操作，也只要对这位减掉查询出来的值即可。

Code

说起来容易，但是，我只想说，这题的代码真的有毒，中间取模你的答案就错了，中间不能取模，也不会爆掉long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
using namespace std;
long long read()
{
	long long x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
const long long mod = 1e9 + 7;
int T;
long long n, m, d;
struct seg_tree
{
	long long s, lazy_tag;
} t[100010 << 2];
long long tpre[100010 << 2];
int lowbit(int x)
{
	return x & -x;
}
void modify(int x, long long y)
{
	while (x <= 100000)
	{
		(tpre[x] += y) %= mod;
		x += lowbit(x);
	}
}
long long getpre(int x)
{
	long long ans = 0;
	while (x)
	{
		(ans += tpre[x]) %= mod;
		x -= lowbit(x);
	}
	return ans;
}
long long a[100010];
inline void pushdown(int root, int len)
{
	if (!t[root].lazy_tag) return;
	t[root << 1].lazy_tag += t[root].lazy_tag;
	t[root << 1 | 1].lazy_tag += t[root].lazy_tag;
	t[root << 1].s += (len - (len >> 1)) * t[root].lazy_tag;
	t[root << 1 | 1].s += (len >> 1) * t[root].lazy_tag;
	t[root].lazy_tag = 0;
}
inline void pushup(int root)
{
	t[root].s = t[root << 1].s + t[root << 1 | 1].s;
}
void build(int root, int l, int r)
{
	if (l == r)
	{
		t[root].s = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(root << 1, l, mid);
	build(root << 1 | 1, mid + 1, r);
	pushup(root);
}
void change(int root, int l, int r, int ll, int rr, long long y)
{
	if (l > rr || r < ll) return;
	if (ll <= l && r <= rr)
	{
		t[root].s += (r - l + 1) * y;
		t[root].lazy_tag += y;
		return;
	}
	pushdown(root, r - l + 1);
	int mid = l + r >> 1;
	if (ll <= mid) change(root << 1, l, mid, ll, rr, y);
	if (rr > mid) change(root << 1 | 1, mid + 1, r, ll, rr, y);
	pushup(root);
}
long long query(int root, int l, int r, int ll, int pos)
{
	if (l > pos || r < ll) return 0;
	if (ll <= l && r <= pos) return t[root].s;
	pushdown(root, r - l + 1);
	int mid = l + r >> 1;
	long long A = 0;
	if (ll <= mid)
		A += query(root << 1, l, mid, ll, pos);
	if (pos > mid)
		A += query(root << 1 | 1, mid + 1, r, ll, pos);
	pushup(root);
	return A;
}
// long long cutt[100010];
int main()
{
	T = read();
	while (T--)
	{
		memset(t, 0, sizeof(t));
		memset(tpre, 0, sizeof(tpre));
		n = read(), m = read(), d = read();
		for (int i = 1; i <= n; ++i) a[i] = read();
		// build(1,1,n);
		for (int i = 1; i <= m; ++i)
		{
			int opt = read();
			if (opt == 1)
			{
				long long x = read(), y = read();
				modify(x, y);
				if (x < n) change(1, 1, n, x + 1, n, 1);
			}
			else
			{
				int x = read();
				// cerr<<"-----"<<t[8].s<<"-----"<<endl;
				long long p = (getpre(x)  + query(1, 1, n, 1, x) * d + a[x]);
				// cerr<<"-----"<<p<<"-----"<<endl;
				printf("%lld\n", p % mod);
				a[x] -= p;
				// cut(1,1,n,x,x,p+a[x]);
				// (((cutt[x] += a[x] + p) %= mod) += mod) %= mod;
				// for(int j=1;j<=n;++j) cerr<<"---"<<a[j]+query(1,1,n,1,j);
				// cerr<<endl;
			}
		}
	}
	return 0;
}
-------------本文结束(づ￣ 3￣)づ~感谢您的阅读(*╹▽╹*)-------------