# Codeforces Round #791 (Div. 2)解题报告(Codeforces round #791 (Div. 2) problem solving Report)-其他

## Codeforces Round #791 (Div. 2)解题报告(Codeforces round #791 (Div. 2) problem solving Report)

### A. AvtoBus

ac 代码

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N = 200010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,m,x,y,k,idx;
int row[N],col[N];
set<int> r;
set<int> co;

int main()
{
ios;
int t;
cin >> t;
while(t --)
{
LL x;
cin >> x;
if(x < 4 || x & 1) cout << -1 << endl;
else
{
LL maxv = x / 4, minv = x / 6 + (x % 6 != 0);
cout << minv << " " << maxv << endl;
}
}
return 0;
}
``````

### B. Stone Age Problem

1.令a[pos] = x;
2.令所有数变成x

ac代码

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N = 2000010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,k;
int a[N];
string s,p;
LL sum = 0,last = 0;
bool flag = false,st[N];
int main()
{
ios;
cin >> n >> k;

for(int i = 1;i <= n;i ++) cin >> a[i],sum += a[i];

while(k --)
{
int t,pos,x;
cin >> t;
if(t == 1)
{
cin >> pos >> x;
if(!flag)
{
sum -= a[pos];
a[pos] = x;
sum +=  a[pos];
}
else
{
if(!st[pos])
{
sum -= last - x;
a[pos] = x;
st[pos] = true;
}
else
{
sum -= a[pos] - x;
a[pos] = x;
}

}
cout << sum << endl;

}
else
{
flag = true;
memset(st,0,sizeof(bool) * (n + 4));
cin >> x;
sum = 1LL * x * n;
last = x;
cout << sum << endl;
}
}
return 0;
}
``````

### C. Rooks Defenders

1.在（x,y）处放一个棋子
2.在（x,y）处取走棋子
3.问 以\((x_1,y_1)\)为左上角\((x_2,y_2)\)为右下角的区域是否每个格子都被攻击

### version 1

ac代码

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N = 200010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,m,x,y,k,idx;
int row[N],col[N];
set<int> r;
set<int> co;
int main()
{
ios;
cin >> n >> k;
for(int i = 1;i <= n;i ++) co.insert(i),r.insert(i);

while(k --)
{
int t,a,b,c,d;
cin >> t;
if(t == 1)
{
cin >> a >> b;
row[a] ++,col[b] ++;

if(row[a] == 1) r.erase(a);
if(col[b] == 1) co.erase(b);
}
else if(t == 2)
{
cin >> a >> b;
row[a] -- , col[b] --;
if(!row[a]) r.insert(a);
if(!col[b]) co.insert(b);
}
else
{
cin >> a >> b >> c >> d;
set<int>::iterator A = r.lower_bound(a),B = co.lower_bound(b);
if(A == r.end() || B == co.end()) cout << "YES" << endl;
else if(* A > c || * B > d) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
return 0;
}
``````

### version 2

ac代码

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N = 200010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,m,x,y,k,idx;
int row[N],col[N];
int tr1[N],tr2[N];

int lowbit(int x)
{
return x & -x;
}

{
for(int i = x;i < N;i += lowbit(i)) tr[i] += v;
}

int query(int tr[],int x)
{
int res = 0;
for(int i = x;i;i -= lowbit(i)) res += tr[i];
return res;
}

int main()
{
ios;
cin >> n >> k;
while(k --)
{
int t,a,b,c,d;
cin >> t;
if(t == 1)
{
cin >> a >> b;
row[a] ++, col[b] ++;
}
else if(t == 2)
{
cin >> a >> b;
row[a] --,col[b] --;
}
else
{
cin >> a >> b >> c >> d;
x = query(tr1,c) - query(tr1,a - 1);
y = query(tr2,d) - query(tr2,b - 1);
if(x >= c - a + 1 || y >= d - b + 1) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
return 0;
}
``````
————————

### A. AvtoBus

There are two kinds of cars, one with four wheels and the other with six wheels. Give you the number of wheels and guess the maximum and minimum number of vehicles that can be exactly composed. If you can’t figure it out, output – 1
Analysis: it is obvious that the odd number of wheels can’t exactly make up several vehicles. Considering the even number, take 6 as two 2 plus one 2, and 4 as two 2, then all even numbers greater than 4 can be regarded as composed of several 2, and all even numbers can be composed of 4 and 6
Therefore, the condition of output – 1 is X & lt; 4 || x & 1. Maximum calculation: if it can be formed, try to form 4 wheels first. If there is a surplus, there must be 2 left. Arbitrarily find a 4-wheel into a 6-wheel, so maxv = x / 4. Minimum calculation: try to form 6 wheels first. If there is a surplus, then the rest is either 2 or 4. Pull out a 6-wheel into two 4 wheels or a 4-6, and the number of vehicles + 1, so minv = x / 6 + (x% 6! = 0);
AC code

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N = 200010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,m,x,y,k,idx;
int row[N],col[N];
set<int> r;
set<int> co;

int main()
{
ios;
int t;
cin >> t;
while(t --)
{
LL x;
cin >> x;
if(x < 4 || x & 1) cout << -1 << endl;
else
{
LL maxv = x / 4, minv = x / 6 + (x % 6 != 0);
cout << minv << " " << maxv << endl;
}
}
return 0;
}
``````

### B. Stone Age Problem

Give you an array to define the following two operations:
1. Make a [POS] = x;
2. Make all numbers X
Each operation outputs the sum of the current array
Analysis: simulation
AC code

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N = 2000010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,k;
int a[N];
string s,p;
LL sum = 0,last = 0;
bool flag = false,st[N];
int main()
{
ios;
cin >> n >> k;

for(int i = 1;i <= n;i ++) cin >> a[i],sum += a[i];

while(k --)
{
int t,pos,x;
cin >> t;
if(t == 1)
{
cin >> pos >> x;
if(!flag)
{
sum -= a[pos];
a[pos] = x;
sum +=  a[pos];
}
else
{
if(!st[pos])
{
sum -= last - x;
a[pos] = x;
st[pos] = true;
}
else
{
sum -= a[pos] - x;
a[pos] = x;
}

}
cout << sum << endl;

}
else
{
flag = true;
memset(st,0,sizeof(bool) * (n + 4));
cin >> x;
sum = 1LL * x * n;
last = x;
cout << sum << endl;
}
}
return 0;
}
``````

### C. Rooks Defenders

Meaning: given a \ (n * n \) chessboard, define the following three operations:
1. Place a piece at (x, y)
2. Remove the chess pieces at (x, y)
3. Ask whether each grid in the area with \ ((x_1, y_1) \) as the upper left corner and \ ((x_2, y_2) \) as the lower right corner is attacked
Attack condition: if there are pieces in the row or column of a grid, it will be attacked
Analysis: maintain two ordered sets of empty rows and empty columns,

### version 1

The binary search tree is used to maintain. Each query finds the smallest element greater than X1 for the ordered row set, and the smallest element greater than Y1 for the sequential set. If the row is greater than x2 or the column is greater than Y2, the whole region is attacked,
AC code

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N = 200010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,m,x,y,k,idx;
int row[N],col[N];
set<int> r;
set<int> co;
int main()
{
ios;
cin >> n >> k;
for(int i = 1;i <= n;i ++) co.insert(i),r.insert(i);

while(k --)
{
int t,a,b,c,d;
cin >> t;
if(t == 1)
{
cin >> a >> b;
row[a] ++,col[b] ++;

if(row[a] == 1) r.erase(a);
if(col[b] == 1) co.erase(b);
}
else if(t == 2)
{
cin >> a >> b;
row[a] -- , col[b] --;
if(!row[a]) r.insert(a);
if(!col[b]) co.insert(b);
}
else
{
cin >> a >> b >> c >> d;
set<int>::iterator A = r.lower_bound(a),B = co.lower_bound(b);
if(A == r.end() || B == co.end()) cout << "YES" << endl;
else if(* A > c || * B > d) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
return 0;
}
``````

### version 2

Maintain empty rows of rows and columns with two tree arrays
AC code

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N = 200010,M = 500010,INF = 0x3f3f3f3f,mod = 1e9 + 7 ;
const double INFF = 0x7f7f7f7f7f7f7f7f;

int n,m,x,y,k,idx;
int row[N],col[N];
int tr1[N],tr2[N];

int lowbit(int x)
{
return x & -x;
}

{
for(int i = x;i < N;i += lowbit(i)) tr[i] += v;
}

int query(int tr[],int x)
{
int res = 0;
for(int i = x;i;i -= lowbit(i)) res += tr[i];
return res;
}

int main()
{
ios;
cin >> n >> k;
while(k --)
{
int t,a,b,c,d;
cin >> t;
if(t == 1)
{
cin >> a >> b;
row[a] ++, col[b] ++;
}
else if(t == 2)
{
cin >> a >> b;
row[a] --,col[b] --;