8.10考试总结
T1
二维偏序模版。
因为
T2
线段树模板。
对于插入和查询，直接操作即可，记得把询问的答案记录起来。
T3
对于每个询问，如果暴力一个一个的找，就会超时。
可以想到倍增。与 LCA 思路完全相同，记录
//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
想到线段树哈希。
用两棵线段树维护即可。一个维护正的哈希值，一个维护反着的。
发现如果会出现不等于的情况则一定可以，所以输出即可。
//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 ;
}