专栏文章

8.10考试总结

HHhy140516
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioejx5s
此快照首次捕获于
2025/12/02 17:55
3 个月前
此快照最后确认于
2025/12/02 17:55
3 个月前
查看原文

T1

二维偏序模版。
因为 yi<yi+1y_i<y_{i+1}，所以对于输入的每个 xix_i，找到比他小的 xjx_j 有多少个，个数加一即可。

T2

线段树模板。
对于插入和查询，直接操作即可，记得把询问的答案记录起来。

T3

对于每个询问，如果暴力一个一个的找，就会超时。
可以想到倍增。与 LCA 思路完全相同，记录 dpi,jdp_{i,j} 即可。
CPP
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
//#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 1e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
struct node
{
  int x , y , id ;
}Node[kMaxN] ;
int n , L , q ;
int a[kMaxN] ;
int dp[33][kMaxN] ;
inline ll ksm(ll a , ll b)
{
	ll mul = 1 ;
	while(b)
	{
		if(b & 1) mul *= a , mul %= MOD ;
		a *= a ;
		a %= MOD ;
		b >>= 1 ;
	}
	return mul ;
}
void work()
{
	cin >> n ;
	for( int i = 1 ; i <= n ; i++ )
	{
		cin >> a[i] ;
	}
	cin >> L >> q ;
	for( int i = 1 ; i <= n ; i++ )
	{
		int l = i , r = n + 1 ;
		while(l + 1 < r)
		{
			int mid = l + r >> 1 ;
			if(a[mid] - a[i] <= L) l = mid ;
			else r = mid ;
		}
		if(a[n] - a[i] <= L) dp[0][i] = n ;
		else dp[0][i] = l ;
	}
	for( int j = 1 ; j <= 30 ; j++ )
	{
		for( int i = 1 ; i <= n ; i++ )
		{
			dp[j][i] = dp[j - 1][dp[j - 1][i]] ;
		}
	}
	while(q--)
	{
		int l , r ;
		cin >> l >> r ;
		if(l > r) swap(l , r) ;
		int res = 0 ;
		for( int i = 30 ; i >= 0 ; i-- )
		{
			if(dp[i][l] < r)
			{
				res += (1 << i) ;
				l = dp[i][l] ;
			}
		}
		cout << res + 1 << "\n" ;
	}
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

T4

想到线段树哈希。
用两棵线段树维护即可。一个维护正的哈希值，一个维护反着的。
发现如果会出现不等于的情况则一定可以，所以输出即可。
CPP
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 3e5 + 5 , MOD = 998244353 , INF = 1e18 , p = 131 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
struct node
{
  int x , y , id ;
}Node[kMaxN] ;
int n ;
int a[kMaxN] ;
ull pw[kMaxN] , hs1[kMaxN << 2] , hs2[kMaxN << 2] ;
inline ll ksm(ll a , ll b)
{
	ll mul = 1 ;
	while(b)
	{
		if(b & 1) mul *= a , mul %= MOD ;
		a *= a ;
		a %= MOD ;
		b >>= 1 ;
	}
	return mul ;
}
#define lson(x) x << 1 
#define rson(x) (x << 1) | 1
void init()
{
	pw[0] = 1 ;
	for( int i = 1 ; i <= 300000 ; i++ )
	{
		pw[i] = pw[i - 1] * p ;
	}
}
void push_up1(int k , int l , int r)
{
	int mid = l + r >> 1 ;
	hs1[k] = hs1[lson(k)] * pw[r - mid] + hs1[rson(k)] ;
}
void update1(int x , ull v , int k , int l , int r)
{
	if(l == r) 
	{
		hs1[k] = v ;
		return ;
	}
	int mid = l + r >> 1 ;
	if(x <= mid) update1(x , v , lson(k) , l , mid) ;
	if(x >= mid + 1) update1(x , v , rson(k) , mid + 1 , r) ;
	push_up1(k , l , r) ;
}
ull query1(int L , int R , int k , int l , int r)
{
	if(L > R) return 0 ;
	if(L <= l && r <= R) 
	{
		return hs1[k] ;
	}
	int mid = l + r >> 1 ;
	int maxn = 0 ;
	if(R <= mid) return query1(L , R , lson(k) , l , mid) ;
	if(L >= mid + 1) return query1(L , R , rson(k) , mid + 1 , r) ;
	return query1(L , R , lson(k) , l , mid) * pw[min(r - mid , R - mid)] + query1(L , R , rson(k) , mid + 1 , r) ;
}
void push_up2(int k , int l , int r)
{
	int mid = l + r >> 1 ;
	hs2[k] = hs2[lson(k)] + pw[mid - l + 1] * hs2[rson(k)] ;
}
void update2(int x , ull v , int k , int l , int r)
{
	if(l == r) 
	{
		hs2[k] = v ;
		return ;
	}
	int mid = l + r >> 1 ;
	if(x <= mid) update2(x , v , lson(k) , l , mid) ;
	if(x >= mid + 1) update2(x , v , rson(k) , mid + 1 , r) ;
	push_up2(k , l , r) ;
}
ull query2(int L , int R , int k , int l , int r)
{
	if(L > R) return 0 ;
	if(L <= l && r <= R) 
	{
		return hs2[k] ;
	}
	int mid = l + r >> 1 ;
	int maxn = 0 ;
	if(R <= mid) return query2(L , R , lson(k) , l , mid) ;
	if(L >= mid + 1) return query2(L , R , rson(k) , mid + 1 , r) ;
	return query2(L , R , lson(k) , l , mid) + pw[min(mid - l + 1 , mid - L + 1)] * query2(L , R , rson(k) , mid + 1 , r) ;
}
void work()
{
	cin >> n ;
	init() ;
	bool flag = 0 ;
	for( int i = 1 ; i <= n ; i++ )
	{
		cin >> a[i] ;
		int len = min(a[i] - 1 , n - a[i]) ;
		if(len >= 1)
		{
			ull ans1 = query1(a[i] - len , a[i] - 1 , 1 , 1 , n) ;
			ull ans2 = query2(a[i] + 1 , a[i] + len , 1 , 1 , n) ;
			if(ans1 != ans2)
			{
				flag = 1 ;
				break ;
			}
		}
		update1(a[i] , 1 , 1 , 1 , n) ;
		update2(a[i] , 1 , 1 , 1 , n) ;
	}
	if(flag) cout << "YES" ;
	else cout << "NO" ;
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...