Post 19

Veröffentlicht am | Edited on

Because of love, even if it hurts to the extreme, we will not be old.

去zyf学姐的blog转了转，找到她在这个时候做的题去做了做，感觉还OK。

然后看到一道二维树状数组的题，就写了写，不过树状数组还是原理重要，显然实现非常简单

BZOJ 1452: [JSOI2009]Count

Description

一个N*M的方格，初始时每个格子有一个整数权值，接下来每次有2个操作:

改变一个格子的权值

求一个子矩阵中某个特定权值出现的个数

Input

每一行有两个数字N，M

接下来N行，每行M个数字。第i+1行第j个数字表示格子(i,j)的初值

接下来输入一个Q，后面Q行每行描述一个操作

操作1:

$1$ x y c，表示将格子(x,y)的值变为c

操作2:

$2 ~x1~ x2~ y1~ y2~ c$，表示询问所有满足格子中数字为c的格子数字

$(n,m<=300,Q<=5000)$

$(1<=x<=N,1<=y<=M,1<=c<=100)$

$(x1<=x<=x2,y1<=y<=y2)$

Output

对于每个操作2,按输入中出现的顺序，依次输出一行一个整数表示所求得的个数

Sample Input

3 3
1 2 3
3 2 1
2 1 3
3
2 1 2 1 2 1
1 2 3 2
2 2 3 2 3 2

Sample Output

1
2

题解

单点修改，查询特定值，较少的询问次数与很小的值域使得这道题目没有任何的难度。

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
/**************************************************************
    Problem: 1452
    User: RBZNO1
    Language: C++
    Result: Accepted
    Time:4592 ms
    Memory:39808 kb
****************************************************************/
 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 305
#define maxk 105
int s[maxn][maxn] , tr[maxk][maxn][maxn] , n , m , q;
inline int query(int t , int x , int y)
{
    int ans = 0;
    if(!x || !y) return ans;
    for(int i = x ; i ; i -= i & -i)
        for(int j = y ; j ; j -= j & -j)
            ans += tr[t][i][j];
    return ans;
}
inline void insert(int val , int x , int y, int v)
{
    for(int i = x ; i <= n; i += i & -i)
        for(int j = y ; j <= m ; j += j & -j)
            tr[val][i][j] += v;
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            scanf("%d",&s[i][j]) , insert(s[i][j] , i , j , 1);
    scanf("%d",&q);
    for(int i = 1 ; i <= q ; ++i)
    {
        int op;
        scanf("%d",&op);
        if( op == 2 ) {
            int x1 , x2 , z1 , z2 , val;
            scanf("%d%d%d%d%d",&x1,&z1,&x2,&z2,&val);
            int a1 = query(val, z1,z2) , a2 = query(val , z1, x2 - 1) , a3 = query(val , x1 - 1 , z2) , a4 = query(val , x1 - 1 , x2 - 1);
            printf("%d\n",a1-a2-a3+a4);
        }
        else if(op == 1){
            int x , y , v;
            scanf("%d%d%d",&x,&y,&v);
            insert(s[x][y] , x , y , -1);
            s[x][y] = v;
            insert(s[x][y] , x , y , 1);
        }
 
    }
}

序列终结者

题目背景

网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……

这样我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。

这道题目就叫序列终结者吧。

题目描述

给定一个长度为N的序列，每个序列的元素是一个整数（废话）。要支持以下三种操作：

  1. 将[L,R][L,R]这个区间内的所有数加上VV。
  2. 将[L,R][L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。
  3. 求[L,R][L,R]这个区间中的最大值。

最开始所有元素都是00。

输入输出格式

输入格式：

第一行两个整数N，M。M为操作个数。

以下M行，每行最多四个整数，依次为K，L，R，V。K表示是第几种操作，如果不是第1种操作则K后面只有两个数。

输出格式：

对于每个第3种操作，给出正确的回答。

输入输出样例

输入样例#1：

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

输出样例#1：

1
2

说明

$N \le 50000,M \le 100000N≤50000,M≤100000。$

题解

这道题调了4个小时。。一道仅仅是Splay扩展了一点的题。

显然还是要充分灵活运用懒标记来维护区间信息。

我们这次换一种简单点的建树方式，直接让节点编号等于下标（显然这随意）

假设我们成功将区间放在根的右孩子的左子树，下面让我们想想如何完成区间操作

显然可以只在根节点打懒标记！只要我们从上面访问到这个节点我们就下推标记，在旋转的时候我们就上传标记。这样既保证复杂度又保证正确性（因为假如树的形态没变，整个子树相对关系没变，进行完全操作是在浪费时间，完全可以等查询的需要时在进行操作，但是假如这个点被访问，并且之后会发生旋转等操作，那么需要下推哦）

同理向上旋转的时候必须pushup。

Splay的懒标记应用非常重要，因此Splay可以支持一切线段树支持的操作，并且支持更高级的一些操作比如区间插入，区间删除等等。

常数较大。

最关键也是坑我4小时的地方是：0号节点在pushup中是存在的（除非你一堆特判），必须赋成-INF！！！！

还有根的右儿子和根节点不需要pushup。

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
129
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 100005
#define ls s[node][0]
#define rs s[node][1]
#define INF 0x7ffffff
#define _DEBUG puts("DEBUG") , print(root);
int s[maxn][2] , f[maxn] , sz[maxn] , id[maxn] , add[maxn] , rev[maxn] , mx[maxn] , v[maxn] , a[maxn] , root , tot , n , m;
inline void pushdown(int node)
{
	if(add[node])
	{
		if(ls)	add[ls] += add[node] , 	mx[ls] += add[node] , v[ls] += add[node];
		if(rs)	add[rs] += add[node] , mx[rs] += add[node],v[rs] += add[node];
		add[node] = 0;
	}
	if(rev[node] )
	{
		if(ls)	rev[ls] ^= 1 ;
		if(rs)	rev[rs] ^= 1;
		rev[node] = 0;
		std::swap(ls, rs);
	}
}
inline void pushup(int node){
	mx[node] = std::max(v[node] , std::max(mx[ls] , mx[rs]));
	sz[node] = sz[ls] + sz[rs] + 1;
}
inline int get(int x){
	return s[f[x]][1] == x;
}
inline void rotate(int node)
{
	int fx = f[node] , ffx = f[fx] , son = get(node);
	s[fx][son] = s[node][son^1] , f[s[node][son^1]] = fx;
	s[node][son^1] = fx , f[fx] = node;
	f[node] = ffx;
	if(ffx) s[ffx][s[ffx][1] == fx] = node;
	pushup(fx) , pushup(node);
}
inline void splay(int node , int pos)
{
	for(int fx ; (fx = f[node]) != pos ; rotate(node))
		if(f[fx] != pos)
			rotate(get(node) == get(fx)? fx : node);
	if(!pos) root = node;
}

void build(int l , int r , int& node , int fa)	
{
	if(l > r) return;
	int mid = l + r >> 1 ;
   	node = mid;
	v[node] = a[mid];
	f[node] = fa;
	build(l , mid - 1 , ls , node);
	build(mid + 1 , r , rs , node);
	pushup(node);
}

inline int find(int x)
{
	int node = root;
	while(node)
	{
		pushdown(node);
		if(sz[ls] >= x) node = ls;
		else{
			x -= sz[ls] + 1;
			if(!x) return node;
			node = rs;
		}
	}
	return -1;
}
inline int split(int l , int r)
{
	int fl = find(l) , fr = find(r + 2);
	splay(fl , 0);
	splay(fr , fl);
	return s[s[root][1]][0];
}
inline void Add(int l , int r, int val)
{
	int node = split(l , r);
	add[node] += val;
	v[node] += val;
	mx[node] += val;
}
inline void Reverse(int l , int r)
{
	int node = split(l , r);
	rev[node] ^= 1;
}
inline int queryMax(int l , int r){
	return mx[split(l,r)];
}

int main()
{
	scanf("%d%d",&n,&m);
	a[1] = a[n+2] = mx[0] = -INF;
	build(1,n + 2 , root , 0);
	for(int i = 1 ; i <= m ; ++i)
	{
		int k;
		scanf("%d",&k);
		if(k == 1){
			int l ,r , t;
			scanf("%d%d%d",&l,&r,&t);
			Add(l , r , t);
		}
		else if(k == 2){
			int l ,r ;
			scanf("%d%d",&l,&r);
			Reverse(l , r);
		}
		else
		{
			int l , r;
			scanf("%d%d",&l,&r);
			int ans = queryMax(l,r);
			printf("%d\n",ans);
		}
	}
}