当前位置: 首页 > news >正文

题解:qoj6504 Flowers Land 2

人类智慧题。

题意:给出一个由 \(0,1,2\) 组成的字符串,每次给出一个区间,使 \(a_i\leftarrow (a_i+1)\mod 3\) 或者询问区间能否通过删除相邻两项使得整个串被删除。

做法:

首先注意到每次一定删除一个奇数位置的一个偶数位置的。然后感觉应该是个线段树题,但是如果直接维护剩下了什么显然是很爆炸的,我们考虑我们现在想要一个东西,他有结合律,但是不满足交换律,否则我乱交换数目对就对了,这显然是不行的。

还真有这么个东西——矩阵,我们考虑直接随三个矩阵 \(A_0,A_1,A_2\) 出来,分别代表 \(0,1,2\) 在奇数位置的权,偶数位置为其逆,修改直接维护 \(+0,+1,+2\) 后的矩阵情况就可以。

实现的时候为了方便,我们可以直接用对合矩阵作为 \(A\),可以省去对奇偶的特判。

代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 5, mod = 998244353;
int qpow(int x, int k, int p) {int res = 1;while(k) {if(k & 1)res = res * x % p;x = x * x % p, k >>= 1;}return res;
}
struct Matrix {int a[2][2], n;Matrix() {memset(a, 0, sizeof(a));}friend Matrix operator*(Matrix x, Matrix y) {Matrix ans; ans.n = x.n;for (int i = 0; i < x.n; i++)for (int j = 0; j < y.n; j++)for (int k = 0; k < x.n; k++)ans.a[i][j] = (ans.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;return ans;}friend bool operator==(Matrix x, Matrix y) {for (int i = 0; i < x.n; i++)for (int j = 0; j < y.n; j++)if(x.a[i][j] != y.a[i][j])return 0;return 1;}void build() {a[1][0] = (1 - a[0][0] * a[0][0] % mod + mod) % mod * qpow(a[0][1], mod - 2, mod) % mod;a[1][1] = mod - a[0][0];}void print() {for (int i = 0; i < 2; i++)for (int j = 0; j < 2; j++)cout << a[i][j] << (j == 1 ? '\n' : ' ');cout << endl;}
};
Matrix ide[3], org;
struct node {Matrix ans[3];friend node operator+(node x, node y) {return node{x.ans[0] * y.ans[0], x.ans[1] * y.ans[1], x.ans[2] * y.ans[2]};}
} ;
int n, m;
string s;
struct Segtree {node tr[maxn << 2];int tag[maxn << 2];void pushup(int t) {tr[t] = tr[t << 1] + tr[t << 1 | 1];}void build(int l, int r, int t) {if(l == r) {for (int cnt = 1, i = s[l] - '0'; cnt <= 3; i = (i + 1) % 3, cnt++)tr[t].ans[cnt - 1] = ide[i];return ;}int mid = l + r >> 1;build(l, mid, t << 1), build(mid + 1, r, t << 1 | 1);pushup(t);}void addtag(int t, int val) {node tp = {tr[t].ans[val], tr[t].ans[(1 + val) % 3], tr[t].ans[(2 + val) % 3]};for (int i = 0; i < 3; i++)tr[t].ans[i] = tp.ans[i];tag[t] = (tag[t] + val) % 3;}void pushdown(int t) {addtag(t << 1, tag[t]);addtag(t << 1 | 1, tag[t]);tag[t] = 0;}void update(int l, int r, int x, int y, int t) {if(x <= l && r <= y) {addtag(t, 1);return ;}int mid = l + r >> 1;pushdown(t);if(x <= mid)update(l, mid, x, y, t << 1);if(mid < y)update(mid + 1, r, x, y, t << 1 | 1);pushup(t);}Matrix query(int l, int r, int x, int y, int t) {if(x <= l && r <= y)return tr[t].ans[0];int mid = l + r >> 1;pushdown(t);if(y <= mid)return query(l, mid, x, y, t << 1);if(mid < x)return query(mid + 1, r, x, y, t << 1 | 1);return query(l, mid, x, y, t << 1) * query(mid + 1, r, x, y, t << 1 | 1);}
} tree;
void prepare() {ide[0].n = ide[1].n = ide[2].n = org.n = 2;org.a[0][0] = org.a[1][1] = 1;ide[0].a[0][0] = 1, ide[0].a[0][1] = 1231;ide[0].build();ide[1].a[0][0] = 123, ide[1].a[0][1] = 23094;ide[1].build();ide[2].a[0][0] = 2348, ide[2].a[0][1] = 98235;ide[2].build();
//	(ide[0] * ide[0]).print();tree.build(1, n, 1);
}
signed main() {cin >> n >> m >> s; s = ' ' + s;prepare();while(m--) {int op, l, r; cin >> op >> l >> r;if(op == 1)tree.update(1, n, l, r, 1);else {cout << (tree.query(1, n, l, r, 1) == org ? "Yes" : "No") << endl;//	tree.query(1, n, l, r, 1).print();}}return 0;
}
http://www.hskmm.com/?act=detail&tid=23585

相关文章:

  • Prophet
  • 深入解析:逻辑回归(Logistic Regression)
  • 和水导学习的第二篇笔记
  • 微信公众号推文添加附件方法,1分钟学会!支持word,excel,pdf等适合招聘,公告,申请表等
  • bMIND包本地安装
  • 为博客写遗言
  • 2025国庆Day2
  • vue - 实战3 - 后端
  • 新能源汽车整车电控环境详解!
  • P11983 [JOIST 2025] 展览会 3 题解
  • 网络流 费用流 EK算法
  • “AI元人文”构想说明:构建智能时代的人文学科新范式
  • 双向LSTM-Attention模型
  • Xilinx高性能NVMe Host控制器IP+PCIe 3.0软核控制器IP,4通道DMA,1通道IO,纯逻辑实现,AXI4和AXI4-Stream DMA接口,支持PCIe 3.0和4.0
  • 公私合作抗击网络威胁的创新实践
  • 特征工程
  • 一些dp题
  • 【人工智能通识专栏】第三十二讲:本地化部署模型 - 教程
  • [Node.js] chokidar 文件系统监听库
  • Jenkins安装并与GitLab集成,实现dev、qa、uat、prod多分支持续集成的详细步骤 - 指南
  • ZR 2025 十一集训 #1
  • Channel-Driven 降低模块耦合设计复杂度
  • how to download a websites favicon.ico
  • mini-spring实现
  • 10.3
  • Linux 代码利用 STDOUT 打印日志导致应用“假死”?一次线上 Bug 的深度排查与解决
  • 2025 年地坪研磨机公司推荐榜单:盘点 TOP 品牌的格力,宁德时代等标杆客户合作案例
  • Python 新手入门:从零开始学习 Python 的 10 个关键步骤
  • EPL S22 Stage 2 赛前前瞻
  • 计算机类毕业设计开题报告注意事项 - 教程