JZTXT

双指针

发布时间 2023-10-27 19:18:36作者: Echo_Long

Andrey and Escape from Capygrad

对于线段的双指针入门题

可以发现对于在 \([l,r]\) 区间的一次询问 要么询问本身呆在原地不动 要么向后跳到 \(b\)

因为跳到的最远点具有单调性 那么我们需要将询问离线排序并用双指针进行统计

\(PS:\) 具有单调性的原因:

假设一个 \(x'>x\) 且 \(x\) 能到达的地方比 \(x'\) 远

那么一定存在一个区间 \([l,r](r<x')\) 使得 \(x\) 可以跳到更远的地方 所以此时的 \(b_i\) 一定大于 \(r\) 和 \(b_i\le r\) 矛盾

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define mid (l+r>>1)
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
const int N = 2e5 + 5;
const int inf = 0x3f3f3f3f;

int read()
{
	int f = 1 , x = 0;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}

int n , qq , ans[N];

struct edge { int l , r , a , b; } a[N];
struct query { int pos , id; } q[N];

signed main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	int T = read();
	while ( T -- )
	{
		n = read();
		for ( int i = 1 ; i <= n ; i ++ ) a[i].l = read() , a[i].r = read() , a[i].a = read() , a[i].b = read();
		qq = read();
		for ( int i = 1 ; i <= qq ; i ++ ) q[i].pos = read() , q[i].id = i;
		sort ( a + 1 , a + n + 1 , [](const edge &a , const edge &b) { return a.l < b.l; } );
		sort ( q + 1 , q + qq + 1 , [](const query &a , const query &b) { return a.pos < b.pos; } );
		int pos = 0 , now = 1;
		for ( int i = 1 ; i <= qq ; i ++ )
		{
			pos = max ( pos , q[i].pos );
			while ( a[now].l <= pos && now <= n ) pos = max ( pos , a[now].b ) , ++ now;
			ans[q[i].id] = pos;
		}
		for ( int i = 1 ; i <= qq ; i ++ ) cout << ans[i] << ' ';
		cout << endl;
	}
	return 0;
}

Cyclic Rotation

玄幻奇妙的题 思想是双指针

我们发现转 \(a\) 比较难 但是我们可以从终止状态 \(b\) 回推

从后往前贪心地匹配 如果遇到了一个不能匹配的点 那么如果 \(b[i]=b[i+1]\) 那么这两个点可以成为一个循环的起始和末尾 用 \(map\) 记录一下

然后继续贪心匹配 如果又遇到了一个不能匹配的点 如果 \(map\) 中有这个数 \(a[i]\) 那么相当于 \(b[i]\) 为起始的这个循环可以转回来 那么我们清除贡献即可

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define mid (l+r>>1)
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
const int N = 3e5 + 5;
const int inf = 0x3f3f3f3f;

int read()
{ 
	int f = 1 , x = 0;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}

int n , a[N] , b[N];
map<int,int> cnt;

signed main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	int T = read();
	while ( T -- )
	{
		cnt.clear();
		int flag = 1;
		n = read(); 
		for ( int i = 1 ; i <= n ; i ++ ) a[i] = read();
		for ( int i = 1 ; i <= n ; i ++ ) b[i] = read();
		int posa = n , posb = n;
		b[n+1]=0;
		while ( posb )
		{
			while ( posa && posb && a[posa] == b[posb] ) -- posa , -- posb;
			// cout << posa << ' ' << posb << endl;
			if ( posa == 0 || posb == 0 ) break;
			if ( b[posb] == b[posb+1] ) cnt[b[posb--]] ++;
			else if ( cnt[a[posa]] ) cnt[a[posa--]] --;
			else { flag = 0; break; }
		}
		cout << ( flag ? "YES" : "NO" ) << endl;
	}
	return 0;
}