《P5522 [yLOI2019] 棠梨煎雪》
题目背景
岁岁花藻檐下共将棠梨煎雪，
自总角至你我某日辗转天边。
天淡天青，宿雨沾襟，
一年一会信笺却只见寥寥数言。
——银临《棠梨煎雪》
题目描述
扶苏正在听《棠梨煎雪》的时候，@spitfirekindergarten 发来一道 IOI2018 集训队作业题：我切了这集训队题，辣鸡扶苏快过来做题。扶苏定睛一看，这不 s* 题嘛，写了一发交上去才发现自己看错题目了。但是写完的代码不能浪费，于是就有了这道题。
歌词中的主人公与她的朋友一年会有一次互相写信给对方，一共通信了 m 年。为了简化问题，我们认为她们每封信的内容都是一条二进制码，并且所有二进制码的长度都是 n。即每封信的内容都是一个长度为 n 的字符串，这个字符串只含字符 0 或 1。
这天她拿出了朋友写给她的所有信件，其中第 i 年的写的信件编号为 i。由于信件保存时间过久，上面有一些字符已经模糊不清，我们将这样的位置记为 ?，? 字符可以被解释为 0 或 1。由于她的朋友也是人，符合人类的本质，所以朋友在一段连续的时间中书写的内容可能是相同的。现在她想问问你，对于一段连续的年份区间 [l,r] 中的所有信件，假如朋友在这段时间展示了人类的本质，所写的是同一句话，那么这一句话一共有多少种可能的组成。也即一共有多少字符串 S，满足在这个区间内的所有信件的内容都可能是 S。
一个长度为 n 的只含 0,1,? 的字符串 A 可能是一个字符串 B 当且仅当 B 满足如下条件：
- B 的长度也是 n 。
- B 中只含字符
0,1。 - A 中所有为
0的位置在 B 中也是0。 - A 中所有为
1的位置在 B 中也是1。 - A 中为
?的位置在 B 中可以为0也可以是1。
同时她可能会突然发现看错了某年的信的内容，于是她可能会把某一年的信的内容修改为一个别的只含 0,1,? 的长度为 n 的字符串。
输入格式
每个输入文件中都有且仅有一组测试数据。
输入数据第一行为三个用空格隔开的整数，分别代表代表字符串长度 n，字符串个数 m 和操作次数 q。
下面 m 行，每行是一个长度为 n 的字符串，第 (i+1) 行的字符串 si 代表第 i 年信的内容。
下面 q 行，每行的第一个数字是操作编号 opt。
- 如果 opt=0，那么后面接两个整数 [l, r]，代表一次查询操作。
- 如果 opt=1，那么后面接一个整数 pos，在一个空格后会有一个长度为 n 的字符串 t，代表将第 pos 个字符串修改为新的字符串 t。
输出格式
为了避免输出过大，请你输出一行一个数代表所有查询的答案异或和对 0 取异或的结果。
输入输出样例
输入 #1复制
3 3 5 010 0?0 1?0 0 1 2 0 2 3 1 3 0?? 0 2 3 0 1 3
输出 #1复制
2
说明/提示
样例 1 解释
- 对于第一次询问，只有串
010符合要求。 - 对于第二次询问，由于第二个串的第一位为
0，第三个串的第一位为1，故没有串符合要求。 - 修改后将第三个串修改为
0??。 - 对于第四次询问，有两个串符合要求，分别为
000和010。 - 对于第五次询问，只有
010符合要求。
故答案为 1,0,2,1，他们的异或和再异或 0 的值为 2。
数据规模与约定
本题采用多测试点捆绑测试，共有 7 个子任务。
| 子任务编号 | m= | q= | n= | 子任务分数 |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 5 |
| 2 | 102 | 102 | 10 | 10 |
| 3 | 1003 | 1003 | 10 | 15 |
| 4 | 1004 | 10004 | 30 | 15 |
| 5 | 100005 | 500005 | 1 | 15 |
| 6 | 100006 | 50006 | 30 | 10 |
| 7 | 100007 | 1000007 | 30 | 30 |
对于全部的测试点，保证：
- 1≤m≤105+7，0≤q≤106+7，1≤n≤30。
- 0≤opt≤1，1≤pos≤m，1≤l≤r≤m。
- si,t 的长度均为 n 且只含有字符
0,1,?。 - 输入字符串的总长度不超过 5×106。数据在 Linux 下生成，即换行符不含
\r。
提示
- 请注意常数因子对程序效率造成的影响。
- 请注意数据读入对程序效率造成的影响。
- 请注意输入的问号为嘤文问号，即其 ASCII 值为 63
注: 为减少错误做法的通过率，时限于 2020 年 7 月由 2000ms 改为 1500ms
代码实现;
#include <ctime>
#include <cstdio>
namespace IPT {
const int L = 1000000;
char buf[L], *front=buf, *end=buf;
char GetChar() {
if (front == end) {
end = buf + fread(front = buf, 1, L, stdin);
if (front == end) return -1;
}
return *(front++);
}
}
template <typename T>
inline void qread(T &x) {
char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();
if (lst == '-') x = -x;
}
namespace OPT {
char buf[120];
}
template <typename T>
inline void qwrite(T x, const char aft, const bool pt) {
if (x < 0) {
x = -x, putchar('-');
}
int top=0;
do {
OPT::buf[++top] = static_cast<char>(x % 10 + '0');
} while (x /= 10);
while (top) putchar(OPT::buf[top--]);
if (pt) putchar(aft);
}
template <typename T>
inline void qr(T &x) {
char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();
if (lst == '-') x = -x;
}
const int maxn = 100010;
int n, m, q;
char s[maxn][35];
#ifdef ONLINE_JUDGE
int Ans;
#endif
struct Tree {
Tree *ls, *rs;
int l, r, x, y;
bool leg;
Tree() {
ls = rs = NULL;
l = r = x = y = 0;
leg = true;
}
void pushup() {
if (!(this->ls->leg && this->rs->leg)) {
this->leg = false;
} else {
if ((this->ls->x & this->rs->x) & (this->ls->y ^ this->rs->y)) {
this->leg = false;
} else {
this->leg = true;
this->x = this->ls->x | this->rs->x;
this->y = this->ls->y | this->rs->y;
}
}
}
};
Tree *rot;
void ReadStr(char *p);
void Update(const int x);
void Query(const int l, const int r);
void update(Tree *const u, const int p);
Tree query(Tree *u, const int l, const int r);
void build(Tree *const u, const int l, const int r);
int main() {
qr(n); qr(m); qr(q);
for (int i = 1; i <= m; ++i) {
ReadStr(s[i] + 1);
}
build(rot = new Tree, 1, m);
int opt, l, r;
while (q--) {
opt = 0; qr(opt);
if (opt == 0) {
l = r = 0; qr(l); qr(r);
Query(l, r);
} else {
l = 0; qr(l);
ReadStr(s[0] + 1);
Update(l);
}
}
#ifdef ONLINE_JUDGE
printf("%d\n", Ans);
#endif
return 0;
}
void ReadStr(char *p) {
do *p = IPT::GetChar(); while ((*p != '0') && (*p != '1') && (*p != '?'));
do *(++p) = IPT::GetChar(); while ((*p == '0') || (*p == '1') || (*p == '?'));
*p = 0;
}
void build(Tree *const u, const int l, const int r) {
if ((u->l = l) == (u->r = r)) {
for (int i = 1; i <= n; ++i) {
if (s[l][i] != '?') {
u->x |= 1 << i;
if (s[l][i] == '1') {
u->y |= 1 << i;
}
}
}
} else {
int mid = (l + r) >> 1;
build(u->ls = new Tree, l, mid);
build(u->rs = new Tree, mid + 1, r);
u->pushup();
}
}
Tree query(Tree *u, const int l, const int r) {
if ((u->l > r) || (u->r < l)) return Tree();
if ((u->l >= l) && (u->r <= r)) return *u;
Tree _ret;
auto ll = query(u->ls, l, r), rr = query(u->rs, l, r);
_ret.ls = ≪ _ret.rs = &rr;
_ret.pushup();
return _ret;
}
void Query(const int l, const int r) {
auto _ret = query(rot, l, r);
if (!_ret.leg) {
#ifndef ONLINE_JUDGE
puts("0");
#endif
} else {
int ans = 1;
for (int i = 1; i <= n; ++i) if (!(_ret.x & (1 << i))) {
ans <<= 1;
}
#ifdef ONLINE_JUDGE
Ans ^= ans;
#else
printf("%d\n", ans);
#endif
}
}
void update(Tree *u, const int p) {
if (u->ls) {
if (u->ls->r >= p) {
update(u->ls, p);
} else {
update(u->rs, p);
}
u->pushup();
} else {
*u = Tree();
u->l = u->r = p;
for (int i = 1; i <= n; ++i) {
if (s[0][i] != '?') {
u->x |= 1 << i;
if (s[0][i] == '1') {
u->y |= 1 << i;
}
}
}
}
}
void Update(const int x) {
update(rot, x);
}