首页 > 其他分享 >2024.10 - 做题记录与方法总结

2024.10 - 做题记录与方法总结

时间:2024-10-02 14:45:06浏览次数:9  
标签:总结 node 2024.10 le cur 记录 int 样例 异或

赏赐的是CCF,收回的也是CCF -《CCF圣经》


2024/10/01

国庆快乐!

P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces

题面:

题目描述

给定一个长度为 \(n=2^k\) 的数组 \(a\),下标从 \(0\) 开始,维护 \(m\) 次操作:

  1. 操作一:给定 \(x\),设数列 \(a'\) 满足 \(a'_i=a_{i\oplus x}\),将 \(a\) 修改为 \(a'\)。其中 \(\oplus\) 表示按位异或运算。
  2. 操作二:给定 \(l,r\),查询 \(a\) 的下标在 \(l,r\) 之间的子数组有多少颜色段。不保证 \(\bm {l\le r}\),若 \(\bm{l > r}\),请自行交换 \(\bm{l,r}\)。

其中,一个极长的所有数都相等的子数组称为一个颜色段。

部分测试点要求强制在线。

输入格式

第一行三个整数 \(T,k,m\),其中 \(T \in \{ 0, 1 \}\) 为决定是否强制在线的参数。

第二行 \(n\) 个整数 \(a_0, \ldots, a_{n-1}\)。

接下来 \(m\) 行,每行两或三个整数,描述一次操作。第一个整数 \(\mathit{op}\) 表示操作类型。

  • 若 \(op=1\),为操作一,接下来一个整数 \(x'\),满足 \(x=x'\oplus(T\times \mathit{lst})\)。
  • 若 \(op=2\),为操作二,接下来两个整数 \(l',r'\),满足 \(l=l'\oplus(T\times \mathit{lst})\),\(r=r'\oplus(T\times \mathit{lst})\)。不保证 \(\bm{l \le r}\),若 \(\bm{l > r}\),请自行交换 \(\bm{l, r}\)。
  • 其中 \(\mathit{lst}\) 表示上次询问的答案。特别地,如果此前没有询问操作,则 \(\mathit{lst}=0\)。
输出格式

输出若干行,每行包含一个整数,依次表示每个询问的答案。

样例 #1
样例输入 #1
0 3 3
1 2 1 3 2 4 5 1
2 1 5
1 3
2 5 1
样例输出 #1
5
4
样例 #2
样例输入 #2
1 3 3
1 2 1 3 2 4 5 1
2 1 5
1 6
2 0 4
样例输出 #2
5
4
样例 #3
样例输入 #3
1 4 16
12 9 5 9 12 12 9 12 9 16 5 9 12 16 9 5
2 0 4
1 15
2 14 0
1 15
2 6 0
2 4 14
1 0
1 14
2 4 10
2 6 3
1 7
2 4 13
1 3
1 3
2 4 3
2 15 2
样例输出 #3
5
7
4
7
9
5
7
2
11
提示

【样例解释 #1】

此样例允许离线。

初始时 \(a=[1,2,1,3,2,4,5,1]\)。

\(a\) 的下标在 \(1,5\) 之间的子数组为 \([2,1,3,2,4]\),它的颜色段数为 \(5\)。

进行重排操作后,\(a=[3,1,2,1,1,5,4,2]\)。

\(a\) 的下标在 \(5,1\) 之间的子数组为 \([1,2,1,1,5]\),它的颜色段数为 \(4\)。

【样例解释 #2】

此样例除强制在线外,与样例 #1 完全一致。

【数据范围】

对于所有测试数据,\(T \in \{ 0, 1 \}\),\(0\le k\le 18\),\(n=2^k\),\(1\le m\le 2\times 10^5\),\(1\le a_i\le n\),\(\mathit{op} \in \{ 1, 2 \}\),\(0\le x,l,r < n\)。

本题采用捆绑测试。

  • Subtask 1(15 points):\(T=1\),\(k\le 10\),\(m\le 10^3\)。
  • Subtask 2(15 points):\(T=1\),不存在操作一。
  • Subtask 3(20 points):\(T=1\),对于所有操作二,要么 \(l=0,r=n-1\),要么 \(l=n-1,r=0\)。
  • Subtask 4(20 points):\(T=0\)。
  • Subtask 5(30 points):\(T=1\)。

注意:Subtask 5 依赖前四个 Subtask,只有通过前四个 Subtask 才能尝试获得该 Subtask 的分数。

全局下标异或上一个 \(x\),查询区间极长颜色段数。

下标范围为 \(\in [0,2^m - 1]\),我们可以先用 01-trie 来理解。

当我们将每个位置的下标伴随着颜色插入到 01-trie 中,如同用线段树一样求间极长颜色段数。

我们不难发现 01-trie 和 线段树 —— 本质是一样的,原因是下标范围恰为 \(\in [0,2^m - 1]\)。

当我们在 01-trie 上判断最高位是否为 \(1 / 0\),和线段树上二分区间 \([0\sim 2^i - 1]\ \ /\ \ [2^i \sim 2^i + (2 ^ i - 1)]\) 是一样的范围。

那我们查询区间极长颜色段数,就上线段树的基本操作:

struct node {
	int lx,rx; // lx <- 最左侧颜色 || rx <- 最右侧颜色
	int ans; // <- 区间极长颜色段数
};

然后,如何合并线段树上区间答案呢?

我们合并区间的时候,只有中间的颜色段会被影响,故:

node merge(node a,node b) {
	node c;
	c.lx = a.lx,c.rx = b.rx;
	c.ans = a.ans + b.ans - (a.rx == b.lx);
	return c;
}

关键问题:如何处理全局下标异或?

下标异或交换————旋转 01-trie!

我们发现如果在 01-trie 上做全局异或操作,

当异或到 \(x\) 的某一位为 \(1\) 时,我们就相当于将左右子树互换,

然后继续向下继续异或操作,并且异或具有交换律,我们只有在询问的时候考虑异或操作。

这个做法看起来很 \(cool\),但遗憾的是,如果我们每一次修改都都做一边上述操作,时间复杂度和暴力无异!

问题出在哪?我们想打 \(tag\) —— 很遗憾,对于一个区间打完 tag 后,我们无法知道区间左右颜色!询问是有问题的。

我们从此发现问题的本质:全局 旋转tag 线段树的问题在于,异或操作是自顶向下的,而下面的操作不实行,答案就无法得出!

我们如何能让下面的答案也清晰起来呢?

神之操作:可持久化!

我们只对询问时的异或和感兴趣,而异或和在 \(\in [0,2^m - 1]\) 之中,

能不能我们直接处理出所有不同异或和版本的线段树?\(exactly!\)

我们对于每一个异或和版本的线段树上可持久化,每一个 \(x\) 版本的线段树来自于 \(x\oplus\operatorname{highbit}(x)\) 版本的线段树。

我们因为在 \(x\oplus\operatorname{highbit}(x)\) 版本上建可持久化线段树,所以我们只有异或到 \(x\) 的 \(\operatorname{highbit}\) 就可以交换左右子树并退出(因为 \(\operatorname{highbit}\) 以下的已经在 \(x\oplus\operatorname{highbit}(x)\) 版本上做过了)

(这是用 \(\mathcal{O}(n\log n)\) 建出每一个异或和版本的线段树的保证)

这样就很好的做到了自下而上的线段树更新!

这样本题就基本上解决了!

AC-code:

#include<bits/stdc++.h>
using namespace std;
int rd() {
	int x = 0, w = 1;
	char ch = 0;
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch - '0');
		ch = getchar();
	}
	return x * w;
}
void wt(int x) {
	static int sta[35];
	int f = 1;
	if(x < 0) f = -1,x *= f;
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	if(f == -1) putchar('-');
	while (top) putchar(sta[--top] + 48);
}
const int N = 3e5+5;
int T,k,m,n,a[N];
int rt[N];
namespace sgt{
#define mid ((pl + pr) >> 1)
struct node {
    int lx,rx,ans;
    node(int l,int r,int a) :lx(l),rx(r),ans(a){}
    node(){}
    friend node operator + (node a,node b) {
        node c;
        c.lx = a.lx;
        c.rx = b.rx;
        c.ans = a.ans + b.ans - (a.rx == b.lx);
        return c;
    }
}t[N * 30];
int ls[N * 30],rs[N * 30],cnt;

int newnode(node x) {
    t[++cnt] = x;
    ls[cnt] = rs[cnt] = 0;
    return cnt;
}

int build(int pl,int pr) {
    if(pl == pr) {
        int cur = newnode(node(a[pl],a[pl],1));
        return cur;
    }
    int cur = newnode(node());
    ls[cur] = build(pl,mid);
    rs[cur] = build(mid+1,pr);
    t[cur] = t[ls[cur]] + t[rs[cur]];
    return cur;
}

int update(int pre,int pl,int pr,int x) {
    int cur = newnode(node());
    int len = (pr - pl + 1);
    if(x & (len >> 1)) {
        ls[cur] = rs[pre],rs[cur] = ls[pre];
    }else {
        ls[cur] = update(ls[pre],pl,mid,x);
        rs[cur] = update(rs[pre],mid+1,pr,x); 
    }
    t[cur] = t[ls[cur]] + t[rs[cur]];
    return cur;
}

node query(int p,int pl,int pr,int l,int r) {
    if(l <= pl && pr <= r) return t[p];
    if(r <= mid) return query(ls[p],pl,mid,l,r);
    else if(l > mid) return query(rs[p],mid+1,pr,l,r);
    else return query(ls[p],pl,mid,l,r) + query(rs[p],mid+1,pr,l,r);
}
    
void init() {
    cnt = 0;
    rt[0] = build(0,n - 1);
    for(int i = 1;i<n;i++) {
        int k = __lg(i);
        rt[i] = update(rt[i ^ (1 << k)],0,n - 1,i);
    }
}

}
int v,lst;
void Reverse() {
    int x = rd();
    x ^= T * lst;
    v ^= x;
}

void query() {
    int l = rd(),r = rd();
    l ^= T * lst,r ^= T * lst;
    if(l > r) swap(l,r);
    lst = sgt::query(rt[v],0,n - 1,l,r).ans;
    wt(lst);
    putchar('\n');
}

signed main() {
    T = rd(),k = rd(),m = rd(),n = (1 << k);
    for(int i = 0;i<n;i++) a[i] = rd();
    sgt::init();
    v = 0,lst = 0;
    while(m--) {
        int opt = rd();
        switch(opt) {
            case 1:
                Reverse();
                break;
            case 2:
                query();
                break;
            default:
                puts("Error");
                exit(0);
                break;
        }
    }
	return 0;
}

标签:总结,node,2024.10,le,cur,记录,int,样例,异或
From: https://www.cnblogs.com/WG-MingJunYi/p/18444727

相关文章

  • 关于Arch Linux 安装及一些相关问题总结
    关于个人ArchLinux安装及相关问题总结关于为什么ssj不得不使用Linux,就其根本地,是因为巨硬的Windows更新炸掉了ssj的蓝牙,Playing的时候只能接入两个设备,难绷0.其它记得在pacstrap前换国内的源不会有人和我一样没换等半天还不成功吧......
  • 10.2 总结
    T1躲避技能赛时拿的是暴力的\(40\)分,没开long。40pts用LCA乱搞,枚举每一个人去哪里,复杂度\(\mathcalO(m!\logn)\)。AC给每一个躲避点打上\(-1\)标记,当前点打上\(1\)标记,每一次向上转移边长乘子树标记和即可。T2奶茶兑换券暴力不会。T3帮助40pts枚举每......
  • 计算机网络 八股记录
    http请求报文,响应报文 301MovedPermanently 和 404NotFound301,服务器会返回新的URL,客户端应该用新的URL进行访问。 502错误意味着代理服务器和上游服务器无法通信,比如上游服务器故障504GatewayTime-out上游服务器响应超时 HTTP的Keep-Alive参数--->长......
  • springboot实战项目-寰宇外卖重难点总结
    思考前端和后端的请求地址不同,前端发送的请求,是如何请求到后端服务的?可以通过nginx反向代理将前端发送的动态请求由nginx转发到后端服务。nginx其他优点:1.提高访问速度。2.进行负载均衡。3.安全性高,保护后端服务安全。nginx负载均衡策略:1.轮询(默认):按时间顺序依次将请求分发......
  • 【训练记录】2024年莆田市高中信息学奥赛国庆集训CSP-S提高组(第二天场外)
    训练情况rk#4\(100+100+100+70=370\)赛后反思没什么很严重的失误,只是国庆早八起不来,打到后面时间不够做第四题了QAQ,下次一定早起TATA题开场怎么是CFDiv4原题,显然因为\(a,b,c,d\)互不相同,最后切出来的结果只有三块或四块,三块的情况是两线没有交叉,四块的情况......
  • 昇腾310P使用记录
    概述课题组最近的项目需要用到华为的昇腾计算卡,和CUDA汗牛充栋的教程和文档相比,作为一款比较新的计算卡产品,昇腾在网上基本没什么教程,可以参考的只有官方文档、官方代码仓库和官方论坛。因此我在使用的过程中,也经过了很多探索,踩了不少坑,所以在这里记录一下我遇到的一些问题和解决......
  • CSP-S/NOIP提高组 真题题解总结
    DP:线性dpP1091[NOIP2004提高组]合唱队形比较简单的一道题。求出以\(i\)结尾的最长上升子序列和以\(i\)为头的最长下降子序列,相加\(-1\)即可。P1052[NOIP2005提高组]过河如果不考虑\(L\)的范围,那么就是一道简单的线性dp。但是\(L\)很大,石头数量很少,......
  • MYSQL查询重复记录的方法
    1、查找表中多余的重复记录,重复记录是根据单个字段(peopleId)来判断select * from people  where peopleId in (select peopleId from people group by peopleId having count(peopleId) > 1)  2、删除表中多余的重复记录,重复记录是根据单个字段(peopleId......
  • 2024/09/30 模拟赛总结
    \(0+0+42+40\),T1在写正解的时候突然比赛还有1分钟结束,然后把freopen注释的暴力在最后几秒交了上去#A.博弈唐氏xor-hashing,首先博弈游戏很简单,如果有一个数的出现次数是奇数则先手必胜,否则先手必败那么先手必败的条件就是路径上所有边权都是两两配对的,即异或和为\(0\)。那......
  • 2024.10.1 总结(集训;数据结构 主要是线段树)
    XK又来给我们讲课了。开心!1.Baka'sTrick两种理解:双栈模拟队列。[找到若干个划分点,使得每个区间包含恰好一个划分点。维护划分点到划分点段的前缀、后缀信息。在在线的实现中,在队列中维护仅仅一个划分点,维护它到前面每个点和它到后面每个点的信息。当这个划分点出队时,把队......