电脑网站与手机的区别,珠海seo推广,网站购买云空间,在线旅游网站开发分析报告B. Lynyrd Skynyrd#xff08;segment tree redouble#xff09;
给定一个长度为nnn的排列ppp#xff0c;一个长度为mmm的数组aaa#xff0c;有mmm次询问#xff0c;每次询问给定l,rl, rl,r#xff0c;问在数组aaa中是否存在一个子序列构成的串是ppp的循环位移串#…B. Lynyrd Skynyrdsegment tree redouble
给定一个长度为nnn的排列ppp一个长度为mmm的数组aaa有mmm次询问每次询问给定l,rl, rl,r问在数组aaa中是否存在一个子序列构成的串是ppp的循环位移串
例如pi,pi1,…,pn,p1,p2,…,pi−1p_i, p_{i 1}, \dots, p_{n}, p_1, p_2, \dots, p_{i - 1}pi,pi1,…,pn,p1,p2,…,pi−1就是排列ppp的一个循环位移串。要求输出 mmm个字符第iii个字符为111表示第iii个询问存在循环位移串。
考虑对每个点预处理出如果从这个点开始要构成一个循环位移串最右边需要到哪这里可以用倍增处理
从第iii个点跳2j2 ^ j2j次方能到哪然后对其求一下跳n−1n - 1n−1步能到的位置对每次询问
我们只要知道[l,r][l, r][l,r]区间内是否有一个数≤r\leq r≤r即可可以用线段树维护区间最小值实现所以整体复杂度O(nlogn)O(n \log n)O(nlogn)。
#include bits/stdc.h
#define mid (l r 1)
#define lson rt 1, l, mid
#define rson rt 1 | 1, mid 1, r
#define ls rt 1
#define rs rt 1 | 1using namespace std;const int N 2e5 10;int p[N], pos[N], a[N], last[N], r[N][20], minn[N 2], n, m, q;void update(int rt, int l, int r, int x, int v) {if (l r) {minn[rt] v;return ;}if (x mid) {update(lson, x, v);}if (x mid) {update(rson, x, v);}minn[rt] min(minn[ls], minn[rs]);
}int query(int rt, int l, int r, int L, int R) {if (l L r R) {return minn[rt];}int ans 0x3f3f3f3f;if (L mid) {ans min(ans, query(lson, L, R));}if (R mid) {ans min(ans, query(rson, L, R));}return ans;
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);scanf(%d %d %d, n, m, q);for (int i 1; i n; i) {scanf(%d, p[i]);last[i] m 1, pos[p[i]] i;}for (int i 1; i m; i) {scanf(%d, a[i]);}for (int i m; i 1; i--) {last[a[i]] i;int id pos[a[i]] % n 1;r[i][0] last[p[id]];}for (int i 0; i 20; i) {r[m 1][i] m 1;}for (int j 1; j 20; j) {for (int i 1; i m; i) {r[i][j] r[r[i][j - 1]][j - 1];}}memset(minn, 0x3f, sizeof minn);for (int i 1; i m; i) {int p i, last n - 1;for (int j 19; j 0; j--) {if (last (1 j)) {p r[p][j];last - 1 j;}}update(1, 1, m, i, p);}for (int i 1, l, r; i q; i) {scanf(%d %d, l, r);putchar(query(1, 1, m, l, r) r ? 1 : 0);}return 0;
}
