Codeforces Global Round 21A~D

A. NIT orz!

The question ：
Given a length of $n$ Array of , And give an integer $z$, You can do the following ：
$a[i]=zORa[i],z=zANDa[i]$
After operation ( Or no operation ) Array a The maximum of
Ideas ：
If you operate $z$ It's just getting smaller , So only in the first operation ,$a[i]$ Will be as big as possible , So enumerate all $a[i]ORz$ For maximum

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){
    return (a%mod+mod)%mod;}
LL lowbit(LL x){
    return x&-x;}// Its lowest 1 And behind it 0 The value of composition 
LL qmi(LL a,LL b,LL mod) {
    LL ans = 1; while(b){
     if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n,z;
const int N=2010;
int a[N];
void solve()
{
    
	cin>>n>>z;
	for(int i=1;i<=n;i++)cin>>a[i];
	int maxv=0;
	for(int i=1;i<=n;i++)
	{
    
		maxv=max(maxv,a[i]|z);
	}
	cout<<maxv<<endl;
}
signed main()
{
    
    io;
 	cin>>_; 
 	while(_--)
    solve();
    return 0;
}

B. NIT Destroys the Universe

The question ：
Given an array $a$, You can select one for each operation $l,r$, Yes $[l,r]$ Conduct $mex$ operation , Make the array $a$ All become 0 Minimum operands of
Ideas ：
Not for 0 A continuous element of the requires an operation , If there are more than two sections , Just think of it as a whole segment , The conclusion is that the maximum operand does not exceed 2

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){
    return (a%mod+mod)%mod;}
LL lowbit(LL x){
    return x&-x;}// Its lowest 1 And behind it 0 The value of composition 
LL qmi(LL a,LL b,LL mod) {
    LL ans = 1; while(b){
     if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n,m;
int k;
const int N=1e5+10;
int a[N];
void solve()
{
    
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int cnt=0;
	a[0]=0;
	for(int i=0,j=0;i<=n;i++)
	{
    
		if(a[i]==0)j=i;
		else
		{
    
			if(i==j+1)cnt++;
		}
	}
	if(cnt>1)cout<<2<<endl;
	else cout<<cnt<<endl;
}
signed main()
{
    
    io;
 	cin>>_; 
 	while(_--)
    solve();
    return 0;
}

C. Fishingprince Plays With Array

The question ：
Given an array $a$ And an integer $m$, There are two operations

1. If a[i] %m=0, Then you can put a[i] Split m individual a[i]/m.
2. Can be m A continuous a[i] Merge into one m*a[i]
   Judge whether it is possible to a Array to b Array

Ideas ：
take a and b The array should be disassembled as much as possible , because $a_i<=1e9$ So merge the continuous equal
Empathy b An array is , Finally, judge whether they are equal

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){
    return (a%mod+mod)%mod;}
LL lowbit(LL x){
    return x&-x;}// Its lowest 1 And behind it 0 The value of composition 
LL qmi(LL a,LL b,LL mod) {
    LL ans = 1; while(b){
     if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n,m;
int k;
const int N=5e4+10;
int a[N],b[N];
void solve()
{
    
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	cin>>k;
	for(int i=1;i<=k;i++)cin>>b[i];
	vector<PII>v1,v2;
	for(int i=1;i<=n;i++)
	{
    
		int s=1;
		while(a[i]%m==0)s*=m,a[i]/=m;
		if(v1.size()==0||v1.back().x!=a[i])v1.pb({
    a[i],s});
		else v1.back().y+=s;
	}
	for(int i=1;i<=k;i++)
	{
    
		int s=1;
		while(b[i]%m==0)s*=m,b[i]/=m;
		if(v2.size()==0||v2.back().x!=b[i])v2.pb({
    b[i],s});
		else v2.back().y+=s;
	}	
	if(v1==v2)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}
signed main()
{
    
    io;
 	cin>>_; 
 	while(_--)
    solve();
    return 0;
}

D. Permutation Graph

The question ：
Give a certain arrangement ,$1-n$ Out of order , Define two points i, j There is a line with a length of 1 If and only if at i, j The maximum and minimum values in the range of are respectively in $a[i]$ and $a[j]$, But the order can be swapped , Excuse me, $1-n$ The longest section of the road .
Ideas ：
From the perspective of greed , The larger the span, the better , We need to deal with the interval directly （ Find a maximum and minimum at the left and right ends ）, Divide and conquer recursion .

input
10
7 4 8 1 6 10 3 5 2 9
output
6

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){
    return (a%mod+mod)%mod;}
LL lowbit(LL x){
    return x&-x;}// Its lowest 1 And behind it 0 The value of composition 
LL qmi(LL a,LL b,LL mod) {
    LL ans = 1; while(b){
     if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
const int N=2.5e5+10;
int a[N],pos[N];
int n,m,p;
struct node
{
    
	int l,r;
	int minv;
	int maxv;
}tr[4*N];
void pushup(int u)
{
    
	tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);
	tr[u].minv=min(tr[u<<1].minv,tr[u<<1|1].minv);
}
void build(int u,int l,int r)
{
    
	tr[u]={
    l,r};
	if(l==r)
	{
    
		tr[u].minv=tr[u].maxv=a[r];
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
}
int query_min(int u,int l,int r)
{
    
	if(tr[u].l>=l&&tr[u].r<=r)return tr[u].minv;
	int mid=tr[u].l+tr[u].r>>1;
	int v=INF;
	if(l<=mid)v=query_min(u<<1,l,r);
	if(r>mid)v=min(v,query_min(u<<1|1,l,r));
	return v;
}
int query_max(int u,int l,int r)
{
    
	if(tr[u].l>=l&&tr[u].r<=r)return tr[u].maxv;
	int mid=tr[u].l+tr[u].r>>1;
	int v=0;
	if(l<=mid)v=query_max(u<<1,l,r);
	if(r>mid)v=max(v,query_max(u<<1|1,l,r));
	return v;
}
int search(int l,int r)
{
    
	if(l+1==r)return 1;
	if(l>=r)return 0;
	int maxv=query_max(1,l,r);
	int minv=query_min(1,l,r);
	int L=pos[maxv],R=pos[minv];
	if(L>R)swap(L,R);
	return search(l,L)+1+search(R,r);
}
void solve()
{
    
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],pos[a[i]]=i;
	if(n==1)cout<<0<<endl;
	else 
	{
    
		build(1,1,n);
		cout<<search(1,n)<<endl;
	}
}
signed main()
{
    
    io;
 	cin>>_; 
 	while(_--)
    solve();
    return 0;
}