首页 > 其他分享 >火星商店问题 题解

火星商店问题 题解

时间:2024-10-07 09:22:03浏览次数:10  
标签:Oper ch 商店 int 题解 pos Time now 火星

Solution

线段树套 trie,秒了!

\(O(n\log^2 n)\)

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 1e5 + 10;
struct Operation {
	int op, l, r, x, d;
} Oper[N];
int n, m;

#define lc (u << 1)
#define rc ((u << 1) | 1)
#define mid ((l + r) >> 1)

struct BinaryTrie {
	int tot;
	vector<array<int, 2>> ch;
	vector<int> Time;
	BinaryTrie() {
		tot = 1, ch.assign(2, {0, 0}), Time.assign(2, 0);
	}
	void Ins(int x, int d) {
		int pos = 1;
		reo(p, 16, 0) {
			int now = (x >> p) & 1;
			if (!ch[pos][now]) ch[pos][now] = ++tot, ch.push_back({0, 0}), Time.push_back(0);
			pos = ch[pos][now];
			Time[pos] = max(Time[pos], d);
		}
	}
} Trie[N << 2];

void Upd(int u, int l, int r, int x, int v, int d) {
	if (x < l || r < x) return;
	Trie[u].Ins(v, d);
	if (l == r) return;
	Upd(lc, l, mid, x, v, d), Upd(rc, mid + 1, r, x, v, d);
}
vector<array<int, 2>> nodes;
void Get(int u, int l, int r, int x, int y) {
	if (y < l || r < x || x > y) return;
	if (x <= l && r <= y) return nodes.push_back({u, 1});
	Get(lc, l, mid, x, y), Get(rc, mid + 1, r, x, y);
}

#undef lc
#undef rc
#undef mid

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n >> m;
	rep(i, 1, n) {
		int x;
		cin >> x, Upd(1, 1, n, i, x, 100001);
	}
	rep(i, 1, m) {
		cin >> Oper[i].op;
		if (Oper[i].op == 0) {
			cin >> Oper[i].l >> Oper[i].x;
		} else {
			cin >> Oper[i].l >> Oper[i].r >> Oper[i].x >> Oper[i].d;
		}
	}
	for (int day = 1, i = 1; i <= m; ++day) {
		if (Oper[i].op == 0)
			Upd(1, 1, n, Oper[i].l, Oper[i].x, day), ++i;
		for (; i <= m && Oper[i].op == 1; ++i) {
			int l = Oper[i].l, r = Oper[i].r, x = Oper[i].x, d = day - Oper[i].d + 1, ans = 0;
			Get(1, 1, n, l, r);
			reo(t, 16, 0) {
				int now = !((x >> t) & 1), ok = 0;
				for (auto p : nodes) {
					int v = Trie[p[0]].ch[p[1]][now];
					if (v && Trie[p[0]].Time[v] >= d) {
						ok = 1;
						break;
					}
				}
				if (ok) {
					ans |= (1 << t);
					for (auto & p : nodes) {
						int v = Trie[p[0]].ch[p[1]][now];
						if (v && Trie[p[0]].Time[v] >= d) {
							p[1] = v;
						} else {
							p[1] = 0;
						}
					}
				} else {
					now = !now;
					for (auto & p : nodes) {
						int v = Trie[p[0]].ch[p[1]][now];
						if (v && Trie[p[0]].Time[v] >= d) {
							p[1] = v;
						} else {
							p[1] = 0;
						}
					}
				}
			}
			nodes.clear();
			cout << ans << '\n';
		}
	}
	return 0;
}

标签:Oper,ch,商店,int,题解,pos,Time,now,火星
From: https://www.cnblogs.com/laijinyi/p/18449774

相关文章

  • Gym 100543G Virus synthesis 题解
    Solution首先只考虑回文串的答案;我们重点考虑的是偶回文串结论:对于偶回文串\(u\),从其最长的长度小于等于他的一半的回文后缀,或其父亲转移过来,一定是最优的证明:设\(u\)的一个回文子串为\(v\)(不是父亲),你要让\(v\tou\)的转移最优首先\(v\)不能跨过\(u\)的中点,因为此......
  • LOJ 6041 事情的相似度 题解
    Statement先把串reverse,多次给\(l,r\),求\[\max_{l\lei<j\ler}\{\text{LCP}(i,j)\}\]Solution\(\text{sqrtlog}\sim\text{sqrt}\):莫队+线段树/树状数组/set,用SA做\(nm/\omega\):bitset乱搞\(\log^2\):SAM+LCT+BIT在parent树上,LCP等于LCA的......
  • P3332 K大数查询 题解
    Solution整体二分板子题vector太好写了111#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<=(k);++i)#definereo(i,j,k)for(inti=(j);i>=(k);--i)typedeflonglongll;constintN=50010;intn,m,ans[......
  • P4093 序列 题解
    Statement给出\(n\) 个数的序列\(\{a_i\}\),接下来\(m\)秒中每一秒会有一个数发生变化,然后恢复。问最长的子序列长度,使得任意时刻这个子序列不下降。\(n\le10^5\)Solution设\(b_i\)为\(i\)最小能变成的数,\(c_i\)为\(i\)最大能变成的数\[f(i)=\max_{j<i\landc......
  • P4690 镜中的昆虫 (动态区间颜色数) 题解
    Statement区间涂颜色区间颜色数Solution\(O(\text{polysqrt})\)略。\(O(\text{polylog})\)颜色段均摊有两层含义:随机数据下:任意时刻的颜色段个数期望\(O(\logn)\)非随机数据下:每次推平时访问的颜色段个数均摊\(O(n)\)首先维护每个点\(i\)的\(pre_i\),一次询......
  • Codeforces Rund 977 div2 个人题解(A~E1)
    CodeforcesRund977div2个人题解(A,B,C1,C2,E1)Dashboard-CodeforcesRound977(Div.2,basedonCOMPFEST16-FinalRound)-Codeforces火车头#define_CRT_SECURE_NO_WARNINGS1#include<algorithm>#include<array>#include<bitset>#includ......
  • 【题解】C - STEP
    目录题目内容DescriptionInputOutput数据规模与约定做法一思路代码做法2思路代码题目内容原题:洛谷P6492Description给定一个长度为\(n\)的字符序列\(a\),初始时序列中全部都是字符L。有\(q\)次修改,每次给定一个\(x\),若\(a_x\)为L,则将\(a_x\)修改成R,否则将\(a_x\)......
  • 常见问题解决 --- maven手动安装依赖jar包报错
    报错内容:执行命令mvninstall:install-file-DgroupId=com.beidouapp-DartifactId=SSDK-Dversion=4.0.2.0 -Dfile=C:\1\SSDK-Release-4.0.2.0.jar-Dpackaging=jar报错Unknownlifecyclephase“.ggstar“.Youmustspecifyavalidlifecyclephaseoragoal原因:在pow......
  • CCF-CSP认证资格考试题解系列——第4次第2题数字排序
    #include<iostream>#include<algorithm>usingnamespacestd;structre{ intvalue;//数值 intnum;//次数}re[1010];boolcmp(structrea,structreb){ if(a.num==b.num)returna.value<b.value;//次数相同是小的优先 returna.num>b.num;//次数不相同是次数优......
  • CCF-CSP认证资格考试题解系列——第4次第3题节日
    #include<iostream>usingnamespacestd;intm[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};intis_run(intyear){ if(year%400==0||(year%4==0&&year%100))return1; return0;}intgetdays(intyear,intmonth){ if(month==2)returnm[month]+i......