Post 33

Veröffentlicht am

这是成王败寇的残酷。

LOJ#6281. 数列分块入门 5

题目描述

给出一个长为 nn 的数列 a_1\ldots a_na1…an，以及 nn 个操作，操作涉及区间开方，区间求和。

输入格式

第一行输入一个数字 nn。

第二行输入 nn 个数字，第 ii 个数字为 a_iai，以空格隔开。

接下来输入 nn 行询问，每行输入四个数字 \mathrm{opt}, l, r, copt,l,r,c，以空格隔开。

若 \mathrm{opt} = 0opt=0，表示将位于 [l, r][l,r] 的之间的数字都开方。对于区间中每个 a_i(l\le i\le r),\: a_i ← \left\lfloor \sqrt{a_i}\right\rfloorai(l≤i≤r),ai←⌊ai⌋

若 \mathrm{opt} = 1opt=1，表示询问位于 [l, r][l,r] 的所有数字的和。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例

样例输入

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

样例输出

1
2
6
2

数据范围与提示

对于 $100\%$的数据，$1 \leq n \leq 50000$。

题解

这道题倒是不难想，不过还是犯了两个sb错误WA了好几遍。。。

先说思路，我们可以思考如何在线维护每块的和。

说出来你可能不信，我们暴力给所有数开方。

什么？那不TLE？
这里就用到分块的思想了，考虑到每个修改被分块后就只有两个不完整的。

不完整的肯定要暴力开方并且维护块内元素和。

完整的呢？
也暴力开方维护块内元素和，不过由于是完整的块，我们可以标记这个块被标记了几遍，假如被标记次数过多（大概8次）就可以确定这个块内元素非0即1。（注意可以是0，思维一定要缜密）

查询的时候就可以按照分块的方法大段查询小段暴力就可以了。

bug如下：
img

显然整块计算应该是nl，nr。。

导致结果偏大的不止这个，另一个必须静态查错才行（对拍几乎不可能拍出来，除非你知道错误）：

有0的话那个数开多少次都是0，我标记到一定次数直接把块的和赋值为长度了，然后就偏大了。。。

然后就没有其他错误了。

这道题最重要的是没有任何增量运算，因此抓住这点结合开方后的数快速变小的特点不难设计出这个算法

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
#define _Max 50005
#define _MaxSqrt 345
int L[_MaxSqrt] , R[_MaxSqrt] , pos[_Max] , tag[_MaxSqrt] , n , v[_Max] , sum[_MaxSqrt] , blsize , blnum;

inline int getsqrt(int k , int t)
{
	if(t > 6) return 0;
	for(int i = 1 ; i <= t; ++i)
		k = (int)std::sqrt(k);
	return k;
}

inline void print()
{
	puts("BLOCK INFO");
	for(int i = 1 ; i <= blnum ; ++i)
		printf("L:%d R:%d SUM:%d\n",L[i],R[i],sum[i]);
	puts("ARRAY");
	for(int i = 1 ; i <= n ; ++i)
		printf("%d ",v[i]);
	puts("OUT FINISHED");
}

inline void pre()
{
	blsize = (int)std::sqrt(n);
	blnum = n / blsize;
	for(int i = 1 ; i <= blnum ; ++i)
		L[i] = (i-1) * blsize + 1, R[i] = i * blsize;
	if(R[blnum] < n) ++ blnum , L[blnum] = R[blnum-1] + 1 , R[blnum] = n;
	for(int i = 1 ; i <= blnum ; ++i)
		for(int j = L[i] ; j <= R[i] ; ++j)
			pos[j] = i , sum[i] += v[j];
//	print();
}

inline void update(int l , int r)
{
	if(pos[l] == pos[r])
	{
		for(int i = l ; i <= r ; ++i)
			sum[pos[l]] += (int)std::sqrt(v[i]) - v[i] , v[i] = (int)std::sqrt(v[i]);
		return;
	}

	int nl , nr;
	if(L[pos[l]] == l) nl = l;
	else nl = L[pos[l]+1];
	if(R[pos[r]] == r) nr = r;
	else nr = R[pos[r]-1];

	for(int i = l ; i < nl ; ++i)
		sum[pos[i]] += (int)std::sqrt(v[i]) - v[i] , v[i] = (int)std::sqrt(v[i]);
	for(int i = nr + 1 ; i <= r ; ++i)
		sum[pos[i]] += (int)std::sqrt(v[i]) - v[i] , v[i] = (int)std::sqrt(v[i]);

	if(nl > nr) return;
	
	for(int i = pos[nl] ; i <= pos[nr] ; ++i)
	{
		++tag[i];
		if(tag[i] > 8) continue;
		else if(tag[i] == 8)
		{
			sum[i] = 0;
			for(int j = L[i] ; j <= R[i] ; ++j)
				sum[i] += v[j];
			continue;
		}
		for(int j = L[i] ; j <= R[i] ; ++j)
			sum[i] += (int)std::sqrt(v[j]) - v[j] , v[j] = (int)std::sqrt(v[j]);
	}
	return;
}

inline int query(int l , int r)
{
//	printf("QUERY:%d %d\n",l,r); 
//	print();
	int ans = 0;
	if(pos[l] == pos[r])
	{
		for(int i = l ; i <= r ; ++i)
			ans += v[i];			
		return ans;
	}

	int nl , nr;
	if(L[pos[l]] == l) nl = l;
	else nl = L[pos[l]+1];
	if(R[pos[r]] == r) nr = r;
	else nr = R[pos[r]-1];
	
	for(int i = l ; i < nl ; ++i)
		ans += v[i];
	for(int i = nr + 1 ; i <= r ; ++i)
		ans += v[i];

	if(nl > nr) return ans;
	for(int i = pos[nl] ; i <= pos[nr] ; ++i)
		ans += sum[i];
//	print();
	return ans;
}

int main()
{
//	freopen("data.in","r",stdin);
//	freopen("my.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&v[i]);
	pre();
	for(int i = 1 ; i <= n ; ++ i)
	{
		int op , l , r , val;
		scanf("%d%d%d%d",&op,&l,&r,&val);
		if(op &	1)	printf("%d\n",query(l,r));
		else update(l,r);
	}

}

LOJ#6282. 数列分块入门 6

题目描述

给出一个长为 nn 的数列，以及 nn 个操作，操作涉及单点插入，单点询问，数据随机生成。

输入格式

第一行输入一个数字 nn。

第二行输入 nn 个数字，第 i 个数字为 a_iai，以空格隔开。

接下来输入 nn 行询问，每行输入四个数字 \mathrm{opt}opt、ll、rr、cc，以空格隔开。

若 \mathrm{opt} = 0opt=0，表示在第 ll 个数字前插入数字 rr (cc 忽略)。

若 \mathrm{opt} = 1opt=1，表示询问 a_rar 的值（ll 和 cc 忽略）。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例

样例输入

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

样例输出

1
2
2
3

数据范围与提示

对于 $100\%$的数据，$1 \leq n \leq 100000$

题解

这道题也挺有意思，目前想出来一个做法（应该不随机也没有关系）。

我们应该想到这样一个事实：对于一个数被插入到某个位置，后面会整体移动。

假如我们想使用根号算法优化这个过程，能联想到什么呢？
对下标的懒标记！

设块大小为$S$

我们保证每一块块内的下标有序，维护这个块还要支持插入。

我们想用什么呢？

vector+排序（Splay）！

对于插入点所在块， $O(S)$暴力枚举所有id需要修改的元素，加1后把修改元素和id插进vector然后排序$O(Slogn)$（其实这里可以做到线性，只不过有点麻烦就懒得弄了，其实就是一个模拟。。）。

枚举每一块$O(1)$判断是否在插入点后面（可能你会疑惑为什么不直接访问插入块后面的就行了，一开始分的时候不就是块间下标相对单调升的？别忘了为了防止特殊数据大量集中在一块导致排序等维护块有序的代价过大，我们还有重构操作，具体来说就是可能不断使用后面的vector从而块间相对并不是单调的。反正只要块数量在$O(\sqrt{n})$级别，就可以在时限内完成）

然后枚举每一块，假如最小值加上$tag$在这个点的后面，$tag$就再加一。

我们通过上述操作可以在$O(Slogn+n/S)$的时间内维护块内下标均单调的vector。

让我们分析如何查询。

对于给定的一个位置，我们$O(n/S)$枚举每个块，找到位置所在块，由于下标单调，$O(1)$找到那个元素值相应查询即可。

这样一来块大小取$\sqrt{n}$可过，假如你把vector排序换成手动模拟，那么就可以做到每次严格$O(\sqrt{n})$

代码估计今天都不一定写的完。。

历经千辛万苦终于得到一个TLE的代码，话说又有bug，不过确实是因为本题算法编程复杂度比较高导致的。。

看bug：

img

这里忘了减$tag_{ubl}$确实不是忘了是大脑短路，索性各种调试定位后后想了下该减掉tag

img

这里就是对拍后进行精确数据分析分析出来的了，重构后不要忘了把新块的tag赋成原块的。

然后这是TLE3个点的代码

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#define _Max 200005
#define _MaxSqrt 465
int L[_MaxSqrt] , R[_MaxSqrt] , tag[_MaxSqrt] , a[_Max>>1] , n , blsize , blnum;
struct Node{
	int v , id;
	bool operator < (const Node& x)const{
		return id < x.id;
	}
};
std::vector<Node> bl[_MaxSqrt];

inline void print()
{
	puts("DEBUG INFO");
	printf("BLNUM:%d BLSIZE:%d\n",blnum,blsize);
	for(int i = 1 ; i <= blnum ; ++i)
	{
		printf("BLOCK : %d\n",i);
		printf("THE TAG IS : %d Range: %d %d\n",tag[i],bl[i][0].id+tag[i],bl[i][(int)bl[i].size()-1].id+tag[i]);
		puts("ARRAY ELEMENTS:");
		for(int j = 0 ; j < (int)bl[i].size() ; ++j)
			printf("(%d,%d) ",bl[i][j].v,bl[i][j].id+tag[i]);
		putchar(10);
	}
	puts("DEBUG FINISH");
	puts("");
}


inline void rebuild(std::vector<Node>& v , int k)
{
//	puts("REBUILD!!");
	++blnum;
	while((int)v.size() > blsize)
	{
		bl[blnum].push_back(v[(int)v.size()-1]);
		v.pop_back();
	}
	std::sort(bl[blnum].begin(),bl[blnum].end());
	tag[blnum] = k;
//	print();
}

inline void pre()
{
	blsize = (int)pow(n , 0.5);
	blnum = n / blsize;
	for(int i = 1 ; i <= blnum ; ++i)
		L[i] = (i-1)*blsize + 1, R[i] = i*blsize;
	if(R[blnum] < n) ++blnum , L[blnum] = R[blnum-1] + 1 , R[blnum] = n;
	for(int i = 1 ; i <= blnum ; ++i)
		for(int j = L[i] ; j <= R[i] ; ++j)
			bl[i].push_back((Node){a[j],j});
//	print();
}

inline void printS(const std::vector<Node>& k)
{
	printf("SQRQASR\n");
	printf("%d\n",k.size());
	for(int i = 0 ; i < (int)k.size() ; ++i)
		printf("(%d %d)\n",k[i].v,k[i].id);
}
inline void update(int p , int k)
{
//	printf("UPDATE:%d %d\n",p,k);
	int ubl = 0;
	for(int i = 1 ; i <= blnum ; ++i)
		if((int)bl[i].size() && bl[i][0].id + tag[i] <= p && bl[i][(int)bl[i].size()-1].id + tag[i] >= p){
			ubl = i;
			break;
		}
//	printf("UPD THE UBL : %d\n",ubl);
	for(int i = 0 ; i < (int)bl[ubl].size() ; ++i)
		if(bl[ubl][i].id + tag[ubl] >= p)	++bl[ubl][i].id;
	bl[ubl].push_back((Node){k,p-tag[ubl]});
//	printS(bl[ubl]);
	std::sort(bl[ubl].begin() , bl[ubl].end());
//	printS(bl[ubl]);

//	print();
	for(int i = 1 ; i <= blnum ; ++i)
		if(bl[i][0].id + tag[i] > p)
			tag[i] ++ ;
	if((int)bl[ubl].size() > blsize * 2) rebuild(bl[ubl] , tag[ubl]);
//	print();
}

inline int query(int p)
{
//	puts("DEBUG QUERY");
//	printf("QUERY %d\n",p);
//	print();
	for(int i = 1 ; i <= blnum ; ++i)
	{
//		printf("NOW RANGE:%d %d\n",tag[i] + bl[i][0].id , tag[i] + bl[i][(int)bl[i].size()-1].id);
		if(tag[i] + bl[i][0].id <= p && tag[i] + bl[i][(int)bl[i].size()-1].id >= p)
		{
//			printf("THE BLOCK %d size : %d , range: %d %d",i,bl[i].size() , bl[i][0].id +tag[i], bl[i][(int)bl[i].size()-1].id+tag[i]);
//			for(int j = 0 ; j < (int)bl[i].size() ; ++j)
//				printf("(%d %d)\n",bl[i][j].v,bl[i][j].id+tag[i]);
			return bl[i][p-bl[i][0].id-tag[i]].v;
		}
	}
}

int main()
{
	freopen("data.in","r",stdin);
	freopen("my.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&a[i]);
	pre();
	for(int i = 1 ; i <= n ; ++i)
	{
		int op , p , k , c;
		scanf("%d%d%d%d",&op,&p,&k,&c);
		if(op & 1)	printf("%d\n",query(k));
		else update(p,k);
	}
}

这代码稳健性好像也为0，块设小一点居然会RE。。

真是我写过最麻烦的分块。

做题调试时间还是太长了，ATP和zyf好像都说过这个问题哎。。。

突然想滚回去学文化课了，明明想出正解的复杂度居然还TLE，过分。

再写个莫队的题吧。（带修莫队和莫队差不多，就是稍麻烦点qwq）

NOI.AC #44. color

【题目描述】

给定一串n个珠子，其中每一个珠子的颜色为a[i]，总共有k类颜色珠子标号从1到k。

初始给定一个参数T。询问再给定m个区间l[i]到r[i]，每次询问这个区间有多少颜色的珠子出现了恰好T次。

【输入格式】

第一行四个整数n，m，k，T（1<=n,m,k,T<=5*10^5）。

第二行n个整数，第i个整数为a[i]，表示对应珠子的颜色(1<=a[i]<=k)。

接下来m行，每行两个整数l[i]和r[i],表示询问的区间(1<=l[i]<=r[i]<=n)。

【输出格式】

输出m行，每行一个整数，第i行表示第i次询问的答案。

【样例输入】

1
2
3
4
5
6
7
10 5 5 1
1 5 3 4 2 4 1 2 3 5 
1 10
3 6 
2 8
5 7
6 10

【样例输出】

1
2
3
4
5
0
2
3
3
5

【数据范围】

$1<=n,m,k,T<=5*10^5，1<=a[i]<=k,1<=l[i]<=r[i]<=n.$

题解

可以很轻松的$O(1)$维护转移指针区间答案。

对询问二元组排序即可，可看以前的Post来理解带修莫队

无视500000数据

好像不带修，那就随便过了。。

还是被卡常了一个点，由于内存的catch miss太多导致同样规模的数据一个过了一个T了。。

那就这么着吧。。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <iostream>
#define _MAX 500005
int n , m , t , k , c[_MAX] , v[_MAX] , ans[_MAX] , bl , curans;
struct Query{
	int l , r , id;
	bool operator < (const Query& x)const{
		if(l/bl == x.l/bl) return r < x.r;
		return l/bl < x.l/bl;
	}
}q[_MAX];

inline void read(int& x)
{
	char ch = getchar();
	while(ch > '9' || ch < '0') ch = getchar();
	while(ch <= '9' && ch >= '0')
		x = x * 10 + ch - 48 , ch = getchar();
	return;
}
inline void upd(int col , int ty)
{
	c[v[col]] += ty;
	if(c[v[col]] == t && ty == 1) ++curans;
	if(c[v[col]] == t + 1 && ty == 1) --curans;
	if(c[v[col]] == t-1 && ty == -1) --curans;
	if(c[v[col]] == t && ty == -1) ++curans;
}

inline void solve()
{
	bl = (int)std::sqrt(n);
	std::sort(q+1,q+m+1);
	for(int i = 1 ; i <= m ; ++i)
		q[i].r ++ ;
	int l = 1  , r = 1;
	for(int i = 1 ; i <= m ; ++i)
	{
		while(l < q[i].l) upd(l++ , -1);
		while(l > q[i].l) upd(--l , 1);
		while(r < q[i].r) upd(r++ , 1);
		while(r > q[i].r) upd(--r , -1);
		ans[q[i].id] = curans;
	}
}

int main()
{
	read(n),read(m),read(k),read(t);
	for(int i = 1 ; i <= n ; ++i)
		read(v[i]);		
	for(int i = 1 ; i <= m ; ++i)
		read(q[i].l) , read(q[i].r) , q[i].id = i;
	solve();
	for(int i = 1;  i <= m ; ++i)
		printf("%d\n",ans[i]);
}

今天就到此为止吧qwq。

明天写一道POI（FLAG）