Training for Data Structures

Posted by JHSN on May 11, 2017

2017 UESTC 数据结构专题题解



题目链接:2017 UESTC Training for Data Structures

Content

[CDOJ 1591] A - An easy problem A
[CDOJ 1592] B - An easy problem B
[CDOJ 1597] C - An easy problem C
[CDOJ 1584] D - Washi与Sonochi的约定
[CDOJ 1583] E - 曜酱的心意
[CDOJ 1582] F - 奇迹的魔法啊,再度出现!
[CDOJ 1598] G - 加帕里公园的friends
[CDOJ 1581] H - Rikka的烦恼
[CDOJ 1603] I - BanG Dreamer
[CDOJ 1599] J - wtmsb
[CDOJ 1593] K - 老司机破阵
[CDOJ 1594] L - 老司机的奇幻漂流
[CDOJ 1595] M - 老司机的毒奶
[CDOJ 1586] N - 可以说是非常豹笑了
[CDOJ 1590] O - 当然是选择原谅她
[CDOJ 1600] P - 艾尔大停电
[CDOJ 1601] Q - 艾尔大停电2



[CDOJ 1591] A - An easy problem A

Problem

N个数排成一列,Q个询问,每次询问一段区间内的数的极差是多少。
N(1≤N≤50000), Q(1≤Q≤200000)

Solution

极差 = 最大值 - 最小值
所以用线段树维护区间上的最大值,再用另一颗线段树维护区间上的最小值
直接套了一发 zkw 板子(为了 fb,xjb 套板子,能 A 就行)

Code

#include<cstdio>
#include<algorithm>
using namespace std;

const int MAX=2147483647;
int a[100010], t[400010], tt[400010];  // t->min  tt->max
int M,n,m,i,k,x,y;

void change_min(int x,int w) {for (t[x+=M]=w,x>>=1;x;x>>=1) t[x]=min(t[x << 1],t[(x << 1)+1]);}
void change_max(int x,int w) {for (tt[x+=M]=w,x>>=1;x;x>>=1) tt[x]=max(tt[x << 1],tt[(x << 1)+1]);}
int q_min(int l,int r)
{
	int ans=MAX;
	for (l=l+M-1,r=r+M+1;(r-l)!=1;l>>=1,r>>=1)
	{
		if ((l&1)==0) ans=min(ans,t[l+1]);
		if ((r&1)==1) ans=min(ans,t[r-1]);
	}
	return ans;
}
int q_max(int l,int r)
{
	int ans=0;
	for (l=l+M-1,r=r+M+1;(r-l)!=1;l>>=1,r>>=1)
	{
		if ((l&1)==0) ans=max(ans,tt[l+1]);
		if ((r&1)==1) ans=max(ans,tt[r-1]);
	}
	return ans;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (M=1;M<n+2;M<<=1);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		change_min(i,a[i]);
		change_max(i,a[i]);
	}
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		if (x > y) swap(x, y);
		printf("%d
",q_max(x, y) - q_min(x, y));
	}
	return 0;
}




[CDOJ 1592] B - An easy problem B

Problem

维护一段 01 序列,两种操作:
1. 将某一区间的值 01 反转
2. 询问某一区间中最大的均为 1 的连续序列有多长

询问与序列大小均 <= 10^5

Solution

目标序列为最大的均为 1 的连续序列,考虑二分一个区间,则该区间的目标序列可能在左区间,也可能在右区间,也可能横跨两个区间
换句话说,ans = max( 左区间的目标序列,右区间的目标序列,左区间右边界开头的目标序列 + 右区间左边界开头的目标序列 )
所以用线段树来维护区间上的左边界开头的目标序列(L)、右边界开头的目标序列(R)、目标序列(M),因为会有反转操作,所以不仅仅要维护最大的均为 1 的连续序列,还要维护最大的均为 0 的连续序列,这样的话在反转的时候,只要交换两类线段树上相应的节点即可完成线段树上的维护。

具体转移方程(以 1 为例):
L
当左区间全为 1 时,L[x] = len(left_son) + L[right_son]
当左区间不全为 1 时,L[x] = R[left_son]
R
当右区间全为 1 时,R[x] = R[left_son] + len(right_son)
当右区间不全为 1 时,R[x] = R[right_son]
M
M[x] = max(M[left_son], M[right_son], R[left_son] + L[right_son])

与此同时,对于区间修改,需要打标记来减小时间复杂度(此处用 lazy[x] 来表示 x 的儿子是否需要反转)

Code

#include<cstdio>
#include<algorithm>
using namespace std;
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
const int N=100010;
const int N4=N << 2;
int tl[2][N4], tr[2][N4], tmm[2][N4];
bool a[N], lazy[N4];
int n, i, j, op, xx, yy, m;
struct re{
    int l=0, r=0, m=0;
};

void read(int &x) { ... }

void init(int k, int l, int r)  // 初始化
{
    int mid = (l+r)>>1;
    if (l < r)
        { init(lson); init(rson); }
    tl[0][k] = tr[0][k] = tmm[0][k] = r - l + 1;
}

void swapAll(int k)  // 树上反转 01
{
    swap(tl[0][k], tl[1][k]);
    swap(tr[0][k], tr[1][k]);
    swap(tmm[0][k], tmm[1][k]);
}

void pushdown(int k)  // 下传标记
{
    swapAll(k << 1);
    lazy[k << 1] ^= 1;
    swapAll(k << 1 | 1);
    lazy[k << 1 | 1] ^= 1;
    lazy[k] = 0;
}

void pushup(int k, int lenl, int lenr)  // 遍历完子树后更新节点
{
    for (int i = 0; i <= 1; i++)
    {
        if (tmm[i][k << 1] == lenl)
            tl[i][k] = lenl + tl[i][k << 1 | 1];
        else tl[i][k] = tl[i][k << 1];

        if (tmm[i][k << 1 | 1] == lenr)
            tr[i][k] = tr[i][k << 1] + lenr;
        else tr[i][k] = tr[i][k << 1 | 1];

        tmm[i][k] = max(tr[i][k << 1] + tl[i][k << 1 | 1],
                    max(tmm[i][k << 1], tmm[i][k << 1 | 1]));
    }
}

void update(int k, int l, int r, int x, int y)
{
    if (x <= l && r <= y) {
        swapAll(k);
        lazy[k] ^= 1;
        return;
    }
    if (lazy[k]) pushdown(k);
    int mid = (l+r)>>1;
    if (x <= mid) update(lson, x, y);
    if (y > mid) update(rson, x, y);
    pushup(k, mid-l+1, r-mid);
}

re query(int k, int l, int r, int x, int y)
{
    if (x <= l && r <= y)
    {
        re res;
        res.l = tl[1][k];
        res.r = tr[1][k];
        res.m = tmm[1][k];
        return res;
    }
    if (lazy[k]) pushdown(k);
    int mid = (l+r)>>1, lenl = mid-l+1, lenr = r-mid;
    re res1, res2, res;
    if (x <= mid) res1 = query(lson, x, y);
    if (y > mid) res2 = query(rson, x, y);
    pushup(k, lenl, lenr);

    res.l = (res1.m == lenl) ? lenl + res2.l : res1.l;
    res.r = (res2.m == lenr) ? res1.r + lenr : res2.r;
    res.m = max(res1.r + res2.l, max(res1.m, res2.m));  // 转移 res1, res2 得到 res
    return res;
}

int main()
{
    read(n); init(1, 1, n);
    for (i = 1; i <= n; i++) read(a[i]);
    i = 1;
    a[n + 1] = 0;
    while (i <= n)
    {
        while (!a[i] && i <= n) i++;
        j = i;
        while (a[j + 1]) j++;
        if (i <= n) update(1, 1, n, i, j);
        i = j + 1;
    }  // 扫描整一块进行更新,以节约时间
    read(m);
    while (m--)
    {
        read(op); read(xx); read(yy);
        if (op == 1) update(1, 1, n, xx, yy);
        else printf("%d
", query(1, 1, n, xx, yy).m);
    }
    return 0;
}

Note

[HDU 3911]Black And White




[CDOJ 1597] C - An easy problem C

Problem

N个数排成一列(0≤ai≤1e9),有三种操作:
1. 1 L R C 给一段区间内的每个数乘上一个非负整数
2. 2 L R C 给一段区间内的每个数加上一个非负整数
3. 3 L R 询问一段区间的和模上 P(1≤P≤1e9) 的值

以上 C 均满足 0≤C≤1e9

Solution

区间修改,显然和 B 类似,也是线段树打标记的形式
不同的是,这里只需要维护区间和(s),而标记变成了两个,一个是乘(mul),一个是加(add),表示其儿子要乘多少,要加多少(其中乘标记优先级高于加标记)

节点 x 标记下传转移方程:
  s[son] = s[son] * mul[x] + add[x] * len add[son] = add[son] * mul[x] + add[x] mul[son] *= mul[x]
同时清空 x 的标记

加了一点优化,标记下传的条件是 mul[x] != 1 or add[x] > 0

Code

#include<cstdio>
using namespace std;
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
const int N=100010;
const int N4=N << 2;
typedef long long ll;
int op, x, y, n, m, i, oo;
ll ans, c, w1, w2, a[N];
ll s[N4], add[N4], mul[N4];

void read(int &x) { ... }

void init(int k, int l, int r)
{
    mul[k] = 1;
    if (l == r) { s[k] = a[l] % oo; return; }
    int mid = (l + r) >> 1;
    init(lson); init(rson);
    s[k] = (s[k << 1] + s[k << 1 | 1]) % oo;
}

void pushdown(int k, long long len)
{
    s[k << 1] = (s[k << 1] * mul[k] + add[k] * ((len + 1) >> 1)) % oo;
    add[k << 1] = (add[k << 1] * mul[k] + add[k]) % oo;
    mul[k << 1] = (mul[k << 1] * mul[k]) % oo;
    s[k << 1 | 1] = (s[k << 1 | 1] * mul[k] + add[k] * (len >> 1)) % oo;
    add[k << 1 | 1] = (add[k << 1 | 1] * mul[k] + add[k]) % oo;
    mul[k << 1 | 1] = (mul[k << 1 | 1] * mul[k]) % oo;
    mul[k] = 1; add[k] = 0;
}

void update(int k, int l, int r)
{
    if (x <= l && r <= y)
    {
        s[k] = (s[k] * w1 + w2 * (ll)(r - l + 1)) % oo;
        mul[k] = (mul[k] * w1) % oo;
        add[k] = (add[k] * w1 + w2) % oo;
        return;
    }
    if (mul[k] != 1 || add[k] > 0) pushdown(k, r - l + 1);
    int mid = (l + r) >> 1;
    if (x <= mid) update(lson);
    if (y > mid) update(rson);
    s[k] = (s[k << 1] + s[k << 1 | 1]) % oo;
}

long long query(int k, int l, int r)
{
    if (x <= l && r <= y) return s[k];
    if (mul[k] != 1 || add[k] > 0) pushdown(k, r - l + 1);
    int mid = (l + r) >> 1;
    long long res = 0;
    if (x <= mid) res = query(lson);
    if (y > mid) res = (res + query(rson)) % oo;
    s[k] = (s[k << 1] + s[k << 1 | 1]) % oo;
    return res;
}

int main()
{
    read(n); read(oo);
    for (i = 1; i <= n; i++) read(a[i]);
    read(m); init(1, 1, n);
    while (m--)
    {
        read(op); read(x); read(y);
        if (op == 3) printf("%lld
", query(1, 1, n));
        else {
            read(c);
            w1 = (op == 1) ? c : 1;
            w2 = c * (op - 1);
            if (w1 != 1 || w2 > 0) update(1, 1, n);
        }
    }
    return 0;
}

Note

[AHOI 2009]维护序列
[BZOJ 1798]维护序列



[CDOJ 1584] ] D - Washi与Sonochi的约定

Problem

怪物分布在二维平面上,某个怪物的 rank 被定义为 x 坐标不大于其 x 坐标,且 y 坐标不大于其 y 坐标的怪物的数量(不含其自身)。输出 n 行,每行一个整数,分别代表 rank 为 0~n−1 的怪物数量。所有数据在 1~100000 范围内。

Solution

考虑按 x 坐标从小到大(x 坐标一样则按 y 坐标从小到大)扫描,则对于某一个怪物,x 坐标不大于它的怪物都出现在它前面(扫描顺序),所以只要求出当前已扫描的怪物中有多少怪物的 y 坐标是不大于这个怪物即可。这个怪物数量可以用树状数组来维护,套一发板子即可。

Code

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
int ran[N], t[N];
pair<int, int> a[N];
int i, n;

void update(int x) {for (; x < N; x += x & (-x)) t[x]++;}
int sum(int x)
{
    int ans = 0;
    for (; x > 0; x -= x & (-x))
        ans += t[x];
    return ans;
}

int main()
{
    scanf("%d", &n);
    for (i = 1; i <= n; i++) scanf("%d%d", &a[i].first, &a[i].second);
    sort(a + 1, a + n + 1);
    for (i = 1; i <= n; i++)
    {
        ran[sum(a[i].second)]++;
        update(a[i].second);
    }
    for (i = 0; i < n; i++) printf("%d
", ran[i]);
    return 0;
}

Note

肯定是道原题,好像来自 Codeforces,记不太清了
[POJ 2352]Stars




[CDOJ 1583] E - 曜酱的心意

Problem

给定两个大小相同的排列,问最少要交换(只能交换相邻两个)多少次,才能将其中一个排列变成另外一个

Solution

相邻交换次数就是逆序对个数,所以只需要求出排列中的数最后排完会在第几个,对于转换后的序列求逆序对即可,求逆序对用树状数组来维护。

Code

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
int t[N], a[N], b[N], qz[N];
int i, n;

void update(int x) {for (; x < N; x += x & (-x)) t[x]++;}
int sum(int x)
{
    int ans = 0;
    for (; x > 0; x -= x & (-x))
        ans += t[x];
    return ans;
}

int main()
{
    long long ans=0;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]);
        qz[b[i]] = i;  // qz[x] 表示最终序列 x 在第几位
    }
    for (i = 1; i <= n; i++)
    {
        ans += (long long)sum(n) - (long long)sum(qz[a[i]] - 1);
        update(qz[a[i]]);
    }
    printf("%lld
", ans);
    return 0;
}

Note

[NOIP2013 D1T2]火柴排队


[CDOJ 1582] F - 奇迹的魔法啊,再度出现!

Problem

n 个非负整数,m 次询问,每次询问给一个数 x,求 max(ai ^ x) | 1<=i<=n
1≤n,m≤100000
0≤ai,x≤2147483647

Solution

容易得到贪心策略,首先高位补全 0,从 x 的首位开始,必然是高位尽量与其相反是最优的。根据范围,考虑字典树,将每一个数的二进制形式放到 Trie 上,每次询问则按相反的二进制去树上从根开始寻找数,向下走,走到叶子节点为止。

Code

#include<cstdio>
using namespace std;
const int m30=1<<30;
const int Ts=4000010;
int s[Ts][2], f[Ts], a[100010];
// s 记录两个儿子节点位置
// f 记录该节点存储的元素在原序列上的位置
int i, n, k, tot, m;

void add(int x, int y)
{
	int i, j=m30, bj=1, c;
	for (i = 1; i <= 31; i++,j>>=1)
	{
		if (x >= j) c = 1,x -= j;
                else c = 0;
		if (s[bj][c] > 0) bj = s[bj][c];
                        else s[bj][c] = ++tot, bj=tot;
	}
	if (f[bj] == 0) f[bj] = y;
}

int q(int x)
{
	int i, j=m30, bj=1, c;
	for (i = 1; i <= 31; i++,j>>=1)
	{
		if (x >= j) c = 0, x -= j;
                else c = 1;
		if (s[bj][c] > 0) bj = s[bj][c];
					else bj = s[bj][1 - c];
	}
	return f[bj];
}

int main()
{
	scanf("%d", &n);
	tot = 1;
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &k);
		add(k, i);
		a[i] = k;
	}
	scanf("%d", &m);
	for (i = 1; i <= m; i++)
	{
		scanf("%d", &k);
		printf("%d
", a[q(k)] ^ k);
	}
	return 0;
}

Note

大概是原题,曾经在 NOIP 模拟中做过类似的题目



[CDOJ 1598] G - 加帕里公园的friends

Problem

序列 A 有 n(1<=n<=500000) 个数 (|Ai|<=1000),两种操作(操作次数 <= 100000):
1. 1 L R 询问 [L, R] 区间上最大连续子序列和
2. 2 pos X 修改 A[pos] 为 X (|X|<=1000)

Solution

与 B 非常相像,目标为最大连续子序列和,所以考虑维护区间和(S),左边界为序列起点的目标(L),右边界为序列终点的目标(R),任意起点的目标(M)共 4 棵线段树

节点 x 转移方程:
M[x] = max(max(M[lson], M[rson]), R[lson] + L[rson]) L[x] = max(L[lson], S[lson] + L[rson]) R[x] = max(R[rson], R[lson] + S[rson]) S[x] = S[lson] + S[rson]

实际转移的时候需要考虑转移顺序以达到节省空间的效果。因为是单点修改、区间查询,所以使用 zkw 线段树较为方便

Code

#include<cstdio>
#include<cmath>
using namespace std;

const int MAX=1 << 29;
const int Ns=500010;
const int Ms=Ns << 2;
int ts[Ms], tl[Ms], tr[Ms], tm[Ms];
int a[Ns], M, n, m, i, x, y, z, ans, tot, p, q;

inline int max(int x, int y) {return x < y ? y : x;}

void read(int &x) { ... }

void update(int x, int w)
{
    x += M;
    ts[x] = tl[x] = tr[x] = tm[x] = w;
    for (x>>=1; x; x>>=1)
    {
        p = x << 1; q = p | 1;
        tm[x] = max(max(tm[p], tm[q]), tr[p] + tl[q]);
        tl[x] = max(tl[p], ts[p] + tl[q]);
        tr[x] = max(tr[q], tr[p] + ts[q]);
        ts[x] = ts[p] + ts[q];
    }
}

int query(int l, int r)
{
	int ls, ll, lr, lm, rs, rl, rr, rm, y;
	ll = lr = lm = rl = rr = rm = -MAX;
	ls = rs = 0;
	// 询问的时候因为 zkw 的特殊性,需要同时维护这 8 个量(左边 4 个,右边 4 个)
	for (l=l+M-1, r=r+M+1; (r-l)!=1; l>>=1, r>>=1)
	{
		if ((l&1) == 0)
		{
		    y = l | 1;
		    lm = max(max(lm, tm[y]), lr + tl[y]);
		    ll = max(ll, ls + tl[y]);
		    lr = max(tr[y], lr + ts[y]);
		    ls += ts[y];  // 注意转移顺序
        }
		if ((r&1) == 1)
		{
		    y = r ^ 1;
		    rm = max(max(tm[y], rm), tr[y] + rl);
		    rl = max(tl[y], ts[y] + rl);
		    rr = max(tr[y] + rs, rr);
		    rs += ts[y];  // 注意转移顺序
        }
	}
	return max(max(lm, rm), lr + rl);
}

int main()
{
	read(n); read(m);
	for (M = 1; M < n+2; M <<= 1);
	for (i = 1; i <= n; i++)
		{ read(x); update(i, x); }
	lg2 = int(log2(n)) << 1;
	while (m--)
	{
		read(z); read(x); read(y);
		if (z == 2) update(x, y);
        else {
            if (x > y) z = x, x = y, y = z;
            printf("%d
", query(x, y));
        }
	}
	return 0;
}

Note

[Vijos 1083]小白逛公园


[CDOJ 1581] H - Rikka的烦恼

Problem

n(<=70000) 个数组成的序列 A,两种操作(操作数 <= 70000):
1. 0 p v,a[p] += v
2. 0 x0 d,询问 max(a[x0 + kd]) | k 为 非负整数且 x0<=x0+kd<=n

保证任何时刻 abs(Ai)<=2147483647,保证涉及的所有数在 C++ 的 int 范围内

Solution

对于 d 进行分类,分为大公差和小公差(假设界限为 D)。

  • 查询:
    对于大公差(>=D),暴力查询,时间复杂度 O(n / D)。
    对于小公差(<D),我们考虑使用线段树来维护区间最大值,当公差为 d 时,整个序列就被分成了 d 个等差数列,开头分别是 1 ~ d,而且每个序列长 n / d,所以 d 颗线段树空间总和不因 d 改变,也就是说维护公差为 d 的线段树占用的空间是一定的,与 d 无关,所以我们在设计线段树时,可以将公差相同的线段树放在同一行以节约空间。用 tr[d][i] 表示维护公差为 d 且以 Ai(i=1~d) 开头的等差序列的线段树的根节点,那么如果查询 (x0, d),则我们查询的是 tr[d][(x0 - 1) % d + 1] 这颗线段树,则 x0 在这个等差序列中在第 L = (x0 + d - 1) / d 个,整个等差序列有 R = (x0 - 1) / d + (n - x0) / d + 1 个数(x0 左边 + x0 右边 + x0 本身),查询的区间就是 [L, R],时间复杂度为
  • 修改:
    对于每一个修改 (p, v),我们要将涉及到 Ap 的所有线段树都修改一遍,也就是 tr[i][(p - 1) % i + 1] | i = 1..D,相应更新的点就是 (p + i - 1) / i,时间复杂度为

假设查询和修改等概率随机出现,即其次数均为 m / 2,则总时间复杂度为初始化复杂度 + 小公差查询复杂度 + 大公差查询复杂度 + 修改复杂度,假设小公差查询了 x 次,大公差查询了 y 次,修改了 z 次,则总时间复杂度可表示为

且最坏情况下可假设不存在小公差查询,则复杂度可控项为

显然两项相等时时间复杂度最小,即

考虑线段树常数为 k,则

令 C = y / k / (n + m - y),C 大约估计为 6,实测 3 ~ 175 左右均可

另外,因为对于每颗线段树操作都是一样的,不同之处在于线段树根节点(在数组中的起点不同),所以在操作中加入一个指针表示线段树的起点即可兼容所有树。而且因为只有区间查询、单点修改,所以选择使用了 zkw 线段树来减小常数。

Code

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MIN=-2147483648;
const int N=71000;
const int maxD=40;
char ch;
int a[N], t[maxD * (N << 2)], tr[maxD][maxD], M[maxD];
// tr 表示每颗线段树的根节点
int i, j, n, ans, D, x, y, op, m, sizeoft0, tot, len;

void read(int &x) { ... }

void change(int* t, int x, int w, int m)
{for (t[x+=m]+=w,x>>=1; x; x>>=1) t[x] = max(t[x<<1], t[x<<1|1]);}

void update(int xx, int w)
{
    for (int i = 1; i <= D; i++)
        change(&t[tr[i][(xx - 1) % i + 1]], (xx + i - 1) / i, w, M[i]);
}

int query(int* t, int l, int r, int m)
{
    int ans=MIN;
	for (l=l+m-1,r=r+m+1;(r-l)!=1;l>>=1,r>>=1)
	{
		if ((l&1)==0) ans=max(ans,t[l+1]);
		if ((r&1)==1) ans=max(ans,t[r-1]);
	}
	return ans;
}

int main()
{
    read(n);
    D = max(0, int((sqrt(n / 6.0 / log2(n)))));
    tot = 0;  sizeoft0 = sizeof(t[0]);
    for (i = 1; i <= D; i++)
    {
        len = (n + i - 1) / i + 2;
        for (M[i] = 1; M[i] < len; M[i] <<= 1);
        for (j = 1; j <= i; j++)
        	{ tr[i][j] = tot; tot += M[i] << 1; }
    }

    for (i = 1; i <= n; i++)
    	{ read(a[i]); update(i, a[i]); }

    read(m);
    while (m--)
    {
        read(op); read(x); read(y);
        if (op == 0) a[x] += y, update(x, y);
        else if (y >= D) {
                for (ans = MIN, i = x; i <= n; i += y) ans = max(ans, a[i]);
                printf("%d
", ans);
            }
            else printf("%d
", query(&t[tr[y][(x - 1) % y + 1]],
                       (x + y - 1) / y, (n - x) / y + (x - 1) / y + 1, M[y]));
    }
    return 0;
}

Note

很赞的一道题目,想了很久,想到的时候觉得非常巧妙,感谢一发 AutSky_JadeK大爷,让我做到了这么一道需要思考深度而写起来又不复杂的好题。
[BZOJ 3922]


[CDOJ 1603] I - BanG Dreamer

Problem

最少能将一个序列不重复、不遗漏地划分成多少个“堆型子序列”,且输出方案
堆型子序列是指能把整个序列的值映射到一个二叉小根堆上,且子节点比父节点在原序列里的序号更大
多组数据,序列长度不超过 1e5,序列长度总和不超过 2e6,时限 5s

Solution

AutSky_JadeK大爷在群里说了一句 I 题代码巨短,便思考了一下。
考虑从序列开头开始向后扫,依次进行加入堆的操作,这里有一个性质就是,当前判断的这个点,无论接在哪里或者新建堆,它都不会影响后面的节点接到它身上。
每次加入堆时,必须要寻找值比其小的作为其父节点(小根堆性质),其中若有多个选择,则必然是选择值小的不如选择值大的(贪心),若找不到则建一个新堆。
这里有一个疑问是,为什么选择前面的节点,把当前节点接上去,而不是把这个前面的节点让出来给原序列中后面的?不让出来可能会导致后面的节点无处可接而只能建一个新堆。这是因为,这样让出来就会使得当前节点建一个新堆:这是最差的情况,不如让后面的点去考虑是否要建新堆,我们前面的节点能不建就不建,反正有上面那条性质,而且当前节点不能接到后面的节点上。
然后对于寻找最大的比当前节点小的值,可以使用 set 来维护,只要注意额外统计一下每个点后接的点,到了两个把这个点从 set 中删除就行了。

Code

#include<cstdio>
#include<set>
#include<cstring>
#include<algorithm>
using namespace std;
#define fi first
#define se second
const int N=100010;
set <pair<int, int>> t;
set <pair<int, int>>::iterator it;
pair<int, int> p, r[N];
int i, j, k, ans, T, n, x, fa;
int cnt[N];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        t.clear();
        scanf("%d", &n);
        memset(cnt, 0, sizeof(cnt[0]) * (n + 2));
        ans = 0;

        for (i = 1; i <= n; i++)
        {
            scanf("%d", &x);
            r[i].se = i;
            p = make_pair(x, i);
            it = t.upper_bound(p);
            if (it == t.begin() || t.empty())  // 找不到
            {
                r[i].fi = ++ans;  // r.first 保存组别,r.second 保存原序号
                t.insert(p);
            }
            else {
                it--;
                fa = it->se;
                r[i].fi = r[fa].fi;
                t.insert(p);
                cnt[fa]++;
                if (cnt[fa] == 2) t.erase(it);  // 接满了删除
            }
        }
        r[n + 1].fi = r[n + 1].se = 0;
        sort(r + 1, r + n + 1);
        printf("%d
", ans);
        i = 1;
        while (i <= n)
        {
            j = i;
            while (r[j + 1].fi == r[i].fi) j++;
            printf("%d ", j - i + 1);
            for (k = i; k < j; k++)
                printf("%d ", r[k].se);
            printf("%d
", r[j].se);
            i = j + 1;
        }
    }
    return 0;
}

Note

[ZOJ 3963]Heap Partition(2017 ZJU 校赛题)



[CDOJ 1599] J - wtmsb

Problem

果子合并(n<=20000)

Solution

堆,STL 裸题,套板子



[CDOJ 1593] K - 老司机破阵

Problem

有一个长度为 n(n<=100000) 的带权值 (0 ~ 1e9) 的序列,每次选择其中一个元素删除,然后原序列就会断成两截(两个序列)。共删除 n 次,每次删除完后询问 max(序列权值和),例如 1 2 3 4 5,删除 4,断成 1 2 3 和 5,两个中最大的为左边那个序列的权值和,1 + 2 + 3 = 6

Solution

考虑把删除操作倒过来,变为连接,在这个过程中,因为序列值是非负的,所以答案一定是非降的。在连接起来之前判断这个数左右两边是否有序列,如果接起来比当前答案大,则更新。其中,对于这个数两边的序列及其权值和,使用并查集(记录分量权值和)维护。

Code

#include<cstdio>
#include<cstring>
#include<set>
using namespace std;

const int N=100010;
int b[N], f[N];
long long s[N], ans[N], ma;
int cnt, i, n, x, y, fa, p, q;
bool g[N];

int find(int x)
{
    if (f[x] == x) return x;
    f[x] = find(f[x]);
    return f[x];
}

int main()
{
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    	{ scanf("%lld", &s[i]); f[i] = i; }
    for (i = n; i; i--) scanf("%d", &b[i]);
    ma = 0;
    for (i = 1; i <= n; i++)
    {
        ans[n - i + 1] = ma;
        x = b[i]; g[x] = 1;
        if (g[x - 1] && g[x + 1])  // 两边序列都有
        {
            p = find(x - 1);
            q = find(x + 1);
            f[x] = f[q] = p;
            s[p] += s[x] + s[q];
            ma = max(ma, s[p]);
        }
        else if (g[x - 1] || g[x + 1])  // 只有一边
        {
            y = g[x - 1] ? x - 1 : x + 1;
            fa = find(y);
            f[x] = fa;
            s[fa] += s[x];
            ma = max(ma, s[fa]);
        }
        else ma = max(ma, s[x]);  // 都没有,比较该点
    }
    for (i = 1; i <= n; i++) printf("%lld
", ans[i]);
    return 0;
}




[CDOJ 1594] L - 老司机的奇幻漂流

Problem

老司机在救出了女票之后,就和她在全世界旅游,有一天,他们来到了一个神奇的小岛上。
这个小岛上有三种动物,他们互相克制,就像虚空追猎凤凰石头剪刀布一样,他们形成了一个食物环。
热爱小动物的老司机女票已经对这个岛上的N只动物进行了细致的研究,对他们所属的族群也了如指掌,并对他们的行为做了记录。
第一种记录方式是 1 X Y,表示X和Y关系密切(是同类)。
第二种记录方式是 2 X Y,表示X对Y有攻击性行为(X克制Y)。
不过很不凑巧,这些记录被毛手毛脚的JJ给打乱了,使得其中一些记录出现了错误。
为了安慰着急的女票,老司机急忙来帮忙查看是哪些记录出现了错误,当一条记录满足以下三种可能之一时,这就是一条错误的记录。
1)这条记录中的X或者Y比N大
2)攻击性记录中的X攻击了X
3)这条记录与前面的记录相悖
老司机说是来帮忙,但是还要忙着跑去和wyy踢fifa,所以就让你来完成这个任务,找出这些记录中哪些错了。

Solution

带权并查集经典题,0 表示和根节点同类,1 表示能克制根节点,2 表示会被根节点克制
可得几条结论:

  1. A 对 B 的关系为 X,B 对 C 的关系为 Y,则 A 对 B 的关系为 (X + Y) % 3
  2. 第一条结论用两次,即可扩展到四人传递,即 (X + Y + Z) % 3

我比较菜,以上结论都是把所有情况列出来,然后归纳出来的。
然后对于每条记录,先判掉特殊情况 1 和 2,再判掉自己和自己是同类的情况,然后对于 3,先找出它们各自的根节点,如果根节点不同,那是有方法做到不相悖的,不用管;如果相同,那么通过 X-root-Y 关系链以及上面第一条结论计算它们之间的关系,看是否与给出的关系相悖。
如果不相悖,则通过 X-rootx-rooty-Y 关系链以及上面第二条结论计算它们合并后的关系,合并它们两个,合并后不必去更新其子树的状态,将这个操作放到路径压缩中去实现来减小时间复杂度。

Code

#include<cstdio>
#include<cstdlib>
using namespace std;
const int N=50010;
int f[N], i, n, m, x, y, z, p, q, s[N];
bool flag;

int find(int x)
{
    if (f[x] == x) return x;
    int ff = find(f[x]);
    s[x] = (s[x] + s[f[x]]) % 3;
    return f[x] = ff;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++) f[i] = i;

    // 0 same  1 eat-root  2 ate-by-root
    // 0.x=x  1.2=0  1.1=2  2.2=1

    for (i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &z, &x, &y);
        if (x > n || y > n || x <= 0 || y <= 0 || (x == y && z == 2))
            {printf("%d ", i); continue;}
        if (x == y && z == 1) continue;
        p = find(x); q = find(y);
        flag = 0;
        if (p == q && (s[x] + 3 - s[y]) % 3 != z - 1) flag = 1;
        if (flag) printf("%d ", i);
            else f[q] = p, s[q] = (s[x] - (z - 1) - s[y] + 6) % 3;
    }
    return 0;
}

Note

[POJ 1182]食物链


[CDOJ 1595] M - 老司机的毒奶

Problem

有一个每个数各不相同 (>0) 的序列,每次可以选择一个数 X 将其变成 2X 或 2X + 1,给出若干次选择(可以选择同一个数多次)后的序列,问原序列最大值最小可能是多少。例如 3 4 5 6,原序列可能是 (3 4 5 6) (1 2 3 5) (1 2 3 4) …… 其中最小的最大值就是 min(6, 5, 4, ……) = 4
n <= 50000, Ai <= 1e8

Solution

根据贪心原则,肯定是要将最大的数变小,如果无法变小,那么它就是答案。假设它是 X,若 X / 2 还不存在,那么把它变为 X / 2,如果存在了,就看 X / 4 存不存在,以此类推,如果存在 Y = X / 2^k(k 尽量小且大于 0,因为可能这个数把很小的一个位置占掉之后会影响其它数变小),那么就把 X 变成 Y,然后继续选择最大的数,重复以上步骤。

其中选择最大的数使用来堆维护,存不存在使用 map 来维护。

Code

#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;

int i, n, x, t;
map<int, int> m;
priority_queue<int> q;

int main()
{
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        m[x] = 1;
        q.push(x);
    }
    m[0] = 0;

    while (1)
    {
        t = q.top();
        q.pop();
        x = t >> 1;
        while (m.find(x) != m.end() && x > 0) x >>= 1;
        if (x == 0) { printf("%d
", t); return 0; }
        m.erase(t);
        m[x] = 1;
        q.push(x);
    }
    return 0;
}




[CDOJ 1586] N - 可以说是非常豹笑了

Problem

第一行输入一个正整数N(2<=N<=1000000)表示总天数,一个正整数M(1<=M<=1000000)表示给出的关系数。
接下来M行,每行三个整数T(T=1 or 0)、A、B(1<=A,B<=N)。T=1表示在第A天和第B天非常豹的表情一样、T=0表示在第A天和第B天非常豹的表情不一样。非常豹在一天里要么笑了,要么没笑。
输出 ‘YES’ 如果输入是可能的话;输出’NO’ 如果无论怎样都不可能满足输入给出的关系。

Solution

带权并查集,1 表示和根节点表情一样,0 表示和根节点表情不一样。则有结论:
若 A 对 B 的关系为 X,B 对 C 的关系为 Y,则 A 对 B 的关系为 !(X ^ Y)
所以对于每一条关系,与 L 题类似的模式去判断即可,而且这道题目的判断更直接更简单了,详见代码。

Code

#include<cstdio>
#include<cstdlib>
using namespace std;
const int N=1000010;
int f[N], i, n, m, x, y, z, p, q, s[N];

int find(int x)
{
    if (f[x] == x) return x;
    int ff = find(f[x]);
    if (ff != f[x])  // 同样的,子树更新放在了路径压缩里
    {
        s[x] = !(s[x] ^ s[f[x]]);
        f[x] = ff;
    }
    return f[x];
}

void no() { puts("NO"); exit(0); }

int main()
{
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++) f[i] = i, s[i] = 1;
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &z, &x, &y);
        p = find(x);
        q = find(y);
        if (z == 1)
        {
            if (p == q && s[x] != s[y]) no();  // z = 1 表情却不同
            s[q] = !(s[y] ^ s[x]);
        }
        else
        {
            if (p == q && s[x] == s[y]) no();  // z = 0 表情却相同
            s[q] = s[x] ^ s[y];
        }
        f[q] = p;
    }
    puts("YES");
    return 0;
}




[CDOJ 1590] O - 当然是选择原谅她

Note

wobuhui


[CDOJ 1600] P - 艾尔大停电

Problem

N 个矩阵,坐标小数且在 [0, 100000] 范围内,求所有矩阵的并的面积

Solution

矩阵按 X 坐标排序,将每个矩阵的两条平行于 X 轴的边(以下称为横边)小的一条标为 (+),大的一条标为 (-),使用扫描法扫描所有的横边,按 X 坐标从小到大扫,遇到 (+) 边,则标记这一条横线上的这条边所包含的区间,然后这条横线上的所有边扫完后,将标记总和 * 这条横线到下一条横线的距离的乘积加到答案里

  y
  ^
  |
7 |         -----
6 |    ---  XXXXX
5 |    XXX  XXXXX
4 |    XXX  XXXXX
3 |    XXX  XXXXX
2 |    +++  +++++
1 |
  +--------------------> x
O     567  01234

例如这样一个例子,从下往上扫描所有横边,先扫 y=2 的 两条 (+) 边
y=2 这条横线上的标记总和为 3 + 5 = 8,到下一条横线 y=6 距离为 3,所以答案加上 8 * 3
然后扫描 y=6,
遇到一条 (-) 边,标记后横线总和 8 - 3 = 5,到下一条 y=7 距离为 1,所以答案加上 5 * 1
最后扫描 y=7,标记减完至 0

实现:离散化 Y 坐标,对于横线上的标记用线段树来维护(带标记),详见代码

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=110;
const int N8=N << 3;
struct re {
    double y, xx1, xx2;
    bool g;
} a[N];
double xx1, yy1, xx2, yy2, ans, lsh[N8], s[N8];
int t[N8];
int n, i, l, r, w;

inline bool cmp(re a, re b) {return a.y < b.y;}

int find(double x)
{
    int l = 1, r = n, mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if (lsh[mid] < x) l = mid + 1;
                    else r = mid;
    }
    return l;
}

void update(int k, int l, int r, int x, int y)  // w
{
    if (x <= l && r <= y) t[k] += w;
    else {
        int mid = (l + r) >> 1;
        if (x <= mid) update(k << 1, l, mid, x, y);
        if (y > mid) update((k << 1) + 1, mid + 1, r, x, y);
    }
    if (t[k]) s[k] = lsh[r + 1] - lsh[l];
	else s[k] = l == r ? 0 : s[k << 1] + s[(k << 1) + 1];
}

int main()
{
    while (scanf("%d", &n))
    {
        if (!n) break;
        memset(t, 0, sizeof(t[0]) * (n << 3));
        memset(s, 0, sizeof(s[0]) * (n << 3));
        for (i = 1; i <= n; i++)
        {
            scanf("%lf%lf%lf%lf", &xx1, &yy1, &xx2, &yy2);
            a[i << 1].xx1 = a[(i << 1) - 1].xx1 = xx1;
            a[i << 1].xx2 = a[(i << 1) - 1].xx2 = xx2;
            a[i << 1].y = yy1; a[(i << 1) - 1].y = yy2;
            a[i << 1].g = 1;  a[(i << 1) - 1].g = 0;  // 正负的标记
            lsh[i << 1] = xx1; lsh[(i << 1) - 1] = xx2;  // 离散化记录
        }
        n <<= 1;
        sort(lsh + 1, lsh + n + 1);
        sort(a + 1, a + n + 1, cmp);
        ans = 0;
        for (i = 1; i < n; i++)
        {
            l = find(a[i].xx1);
            r = find(a[i].xx2) - 1;  // 用二分查找来确定离散值
            w = a[i].g ? 1 : -1;
            update(1, 1, n, l, r);  // 标记一段区间
            ans += (a[i + 1].y - a[i].y) * s[1];  // s[1] 就是当前的区间总和
        }
        printf("%.2lf
", ans);
    }
    return 0;
}

Note

[CodeVS 3044] 矩形面积并
[POJ 1151]Atlantis 数据太弱,暴力可过



[CDOJ ] Q - 艾尔大停电2

Problem

一片整数格点区域(坐标范围 1 ~ 1000),有两种操作(操作数 <= 50000):
1. C x1 y1 x2 y2 标记一个矩阵区域上的所有点(如果已标记则撤销标记)
2. Q x y 询问某个点是否被标记

多组数据 (T<=10)

Solution

当时看到这个题,一激动套了一发矩阵修改矩阵查询的四个树状数组的板子。。傻逼了

询问可以改为求标记次数,最后次数 % 2 即是答案。
对于每个标记,我们将其转化为增量点来表示,也就是说一个增量点 (x y) 这个点它对 (x..1000, y..1000) 这片区域都有影响,所以 (x1 y1 x2 y2) 可以表示成四个增量点 (x1 y1 +1) (x1 y2+1 -1) (x2+1 y1 -1) (x2+1 y2+1 +1)
这样转化之后,(x y) 的点的标记次数就是增量点 (1..x 1..y) 之和,然后用二维树状数组维护一下矩阵和即可。
同时,因为只需要知道次数 % 2 的值,所以所有的求和操作,都可以换为异或,所有标记操作,都可以换为异或 1 的操作,详见代码。

在 A 掉这道题后,写了另外一种暴力做法——压位暴力,简而言之,就是因为异或这个性质,每个格子只需要保存 0 1 两种状态,所以将连在一起的 block(这里取了 62) 个格子压在一个 long long 里,这样的话每次修改复杂度可以缩减到原来暴力的 block 分之一,最坏复杂度 O(TN * 1000 * 1000 / block) <= 8e9,照道理极限数据是过不了的,不过 OJ 上险过

Code

以下三份代码时耗:77MS 248MS 720MS
压位暴力跑得比矩阵查询快。。论常数的重要性

// 单个树状数组
#include<cstdio>
#include<cstring>
using namespace std;

const int N=1010;
const int Q=50010;
bool t[N][N];
int a[Q][5];
int x, y, xx1, xx2, yy1, yy2, q, maxx, maxy, T, i;

char ch;
void read(int &x)
{
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar());
    for (x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 - 48 + ch;
}

void update(int x, int y)
{
    if (y > maxy) return;
    for (; x <= maxx; x += x & (-x))
        for (int i = y; i <= maxy; i += i & (-i))
            t[x][i] ^= 1;
}
bool sum(int x, int y)
{
    bool res = 0;
    for (; x; x -= x & (-x))
        for (int i = y; i; i -= i & (-i))
            res ^= t[x][i];
    return res;
}

int main()
{
    read(T);
    maxx = 1;
    while (T--)
    {
        memset(t, 0, sizeof(t[0]) * (maxx + 2));
        read(q);
        maxx = maxy = 0;
        for (i = 1; i <= q; i++)
        {
            ch = getchar();
            while (ch != 'Q' && ch != 'C') ch = getchar();
            a[i][0] = (ch == 'C');
            read(a[i][1]); read(a[i][2]);
            if (a[i][1] > maxx) maxx = a[i][1];
            if (a[i][2] > maxy) maxy = a[i][2];
            if (a[i][0])
            {
                read(a[i][3]); read(a[i][4]);
                if (a[i][3] > maxx) maxx = a[i][3];
                if (a[i][4] > maxy) maxy = a[i][4];
            }
        }
        for (i = 1; i <= q; i++)
        {
            if (a[i][0])
            {
                xx1 = a[i][1]; yy1 = a[i][2];
                xx2 = a[i][3]; yy2 = a[i][4];
                update(xx1, yy2 + 1);
                update(xx2 + 1, yy1);
                update(xx2 + 1, yy2 + 1);
                update(xx1, yy1);
            }
            else printf("%d
", sum(a[i][1], a[i][2]));
        }
    }
    return 0;
}
// 压位暴力
#include<cstdio>
#include<cstring>

typedef long long ll;
const int block=62;
const int N=1020;
const int Q=50020;
ll f[N][N / block + 2], left[70], right[70], lmid[70], MAX;
int a[Q][5], i, maxx, q, T, x, y, k, r;

void read(int &x) { ... }

void update(int p1, int q1, int p2, int q2)
{
    int i, j, k, l = q1 / block, r = q2 / block,
                lr = q1 - l * block, rr = q2 - r * block;
    lr = block - 1 - lr;
    for (i = p1; i <= p2; i++)
        if (l != r) {
            for (j = l + 1; j < r; j++) f[i][j] ^= MAX;
            f[i][l] ^= right[lr];
            f[i][r] ^= left[rr];
        }
        else f[i][l] ^= right[lr] & left[rr];
}

int main() {
    lmid[0] = 1ll << (block - 1);
    left[0] = lmid[0]; right[0] = 1;
    for (i = 1; i < block; i++)
    {
        lmid[i] = 1ll << (block - i - 1);  //  lmid[i] = 0..010..0 左数第 i 个为 1
        left[i] = left[i - 1] | lmid[i];   //  left[i] = 1..10..0  左数前 i 个都为 1
        right[i] = (right[i - 1] << 1) | 1;// right[i] = 0..01..1  右数后 i 个都为 1
    }
    MAX = left[block - 1];
    read(T);
    while (T--)
    {
        read(q); maxx = 0;
        memset(f, 0, sizeof(f[0]) * (maxx + 2));
        for (i = 1; i <= q; i++)
        {
            ch = getchar();
            while (ch != 'Q' && ch != 'C') ch = getchar();
            a[i][0] = (ch == 'C');
            read(a[i][1]); read(a[i][2]);
            if (a[i][1] > maxx) maxx = a[i][1];
            if (a[i][0])
            {
                read(a[i][3]); read(a[i][4]);
                if (a[i][3] > maxx) maxx = a[i][3];
            }
        }
        for (i = 1; i <= q; i++)
            if (a[i][0]) update(a[i][1], a[i][2], a[i][3], a[i][4]);
            else
            {
                x = a[i][1]; y = a[i][2];
                k = y / block;
                r = y - k * block;
                printf("%d
", (f[x][k] & lmid[r]) > 0);
            }
    }
    return 0;
}
// 四个树状数组 矩阵修改 矩阵询问
#include<cstdio>
#include<cstring>

typedef long long ll;
const int N=1020;
const int Q=50020;
ll a[N][N], b[N][N], c[N][N], d[N][N], ans;
int f[Q][5], i, maxx, maxy, q, T, x, y;

void read(int &x) { ... }

ll gs(ll a[N][N], int x, int y) {
    ll s = 0; int i;
    for (; x; x -= x&(-x))
        for (i = y; i; i -= i&(-i))
            s += a[x][i];
    return s;
}
void gp(ll a[N][N], int x, int y, ll w)
{
    int i;
    for (; x <= maxx; x += x&(-x))
        for (i = y; i <= maxy; i += i&(-i)) a[x][i] += w;
}

ll sum(ll x, ll y) {
    return (x + 1) * (y + 1) * gs(a, x, y) - (y + 1) * gs(b, x, y)
         - (x + 1) * gs(c, x, y) + gs(d, x, y);
}

void update(int p1, int q1, int p2, int q2, int w) {
    gp(a, p1, q1, w);
    gp(a, p2 + 1, q1, -w);
    gp(a, p1, q2 + 1, -w);
    gp(a, p2 + 1, q2 + 1, w);

    gp(b, p1, q1, w * p1);
    gp(b, p2 + 1, q1, -w * (p2 + 1));
    gp(b, p1, q2 + 1, -w * p1);
    gp(b, p2 + 1, q2 + 1, w * (p2 + 1));

    gp(c, p1, q1, w * q1);
    gp(c, p2 + 1, q1, -w * q1);
    gp(c, p1, q2 + 1, -w * (q2 + 1));
    gp(c, p2 + 1, q2 + 1, w * (q2 + 1));

    gp(d, p1, q1, w * p1 * q1);
    gp(d, p2 + 1, q1, -w * (p2 + 1) * q1);
    gp(d, p1, q2 + 1, -w * p1 * (q2 + 1));
    gp(d, p2 + 1, q2 + 1, w * (p2 + 1) * (q2 + 1));
}

int main() {
    read(T);
    while (T--)
    {
        memset(a, 0, sizeof(a[0]) * (maxx + 2));
        memset(b, 0, sizeof(b[0]) * (maxx + 2));
        memset(c, 0, sizeof(c[0]) * (maxx + 2));
        memset(d, 0, sizeof(d[0]) * (maxx + 2));
        read(q); maxx = maxy = 0;
        for (i = 1; i <= q; i++)
        {
            ch = getchar();
            while (ch != 'Q' && ch != 'C') ch = getchar();
            f[i][0] = (ch == 'C');
            read(f[i][1]); read(f[i][2]);
            if (f[i][1] > maxx) maxx = f[i][1];
            if (f[i][2] > maxy) maxy = f[i][2];
            if (f[i][0])
            {
                read(f[i][3]); read(f[i][4]);
                if (f[i][3] > maxx) maxx = f[i][3];
                if (f[i][4] > maxy) maxy = f[i][4];
            }
        }
        for (i = 1; i <= q; i++)
            if (f[i][0]) update(f[i][1], f[i][2], f[i][3], f[i][4], 1);
            else
            {
                x = f[i][1]; y = f[i][2];
                ans = sum(x, y) - sum(x, y - 1) - sum(x - 1, y) + sum(x - 1, y - 1);
                printf("%lld
", ans & 1);
            }
    }
    return 0;
}

Node

数据太弱,暴力可过,即使后来更新数据,压位暴力仍然可过






评论区加载中