Codeforces Round 882 (Div. 2)
这题很简单的吧，比较脑抽的就是D，下面详细说，我nloglogn过不去2e5说实话有点不应该，感觉有更聪明的办法搞这个。
很奇怪的一点是，yongwham究竟是怎么只做出来A的？？？？
A. The Man who became a God
这题直接优先队列砍m - 1个，没啥说的
代码
#include <bits/stdc++.h>
using namespace std;
constexpr int limit = (2e5 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;
char s = getchar();
while (s > '9' || s < '0') {
if (s == '-')sign = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if (x / 10) print(x / 10);
*O++ = x % 10 + '0';
}
void write(ll x, char c = 't') {
if (x < 0)putchar('-'), x = -x;
print(x);
if (!isalpha(c))*O++ = c;
fwrite(obuf, O - obuf, 1, stdout);
O = obuf;
}
constexpr ll mod = 1e9 + 7;
ll qpow(ll a, ll b){
ll ans = 1;
while (b) {
if (b & 1){
(ans *= a) %= mod;
}
(a *= a) %= mod;
b >>= 1;
}
return ans;
}
int n,m;
int a[limit];
void solve() {
cin>>n>>m;
rep(i,1,n){
cin>>a[i];
}
ll ans = 0;
priority_queue<int>q;
rep(i,1,n -1){
ans += abs(a[i + 1] - a[i]);
q.push(abs(a[i + 1] - a[i]));
}
rep(i,1,m - 1){
ans -= q.top();
q.pop();
}
cout<<ans<<endl;
}
int32_t main() {
#ifdef LOCAL
FOPEN;
// FOUT;
#endif
FASTIO
int kase;
cin>>kase;
while (kase--)
invoke(solve);
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
return 0;
}
B. Hamon Odyssey
这题就是贪心，因为0再去and所有数字都是0，所以不如另起一段，over
代码
#include <bits/stdc++.h>
using namespace std;
constexpr int limit = (2e5 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;
char s = getchar();
while (s > '9' || s < '0') {
if (s == '-')sign = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if (x / 10) print(x / 10);
*O++ = x % 10 + '0';
}
void write(ll x, char c = 't') {
if (x < 0)putchar('-'), x = -x;
print(x);
if (!isalpha(c))*O++ = c;
fwrite(obuf, O - obuf, 1, stdout);
O = obuf;
}
constexpr ll mod = 1e9 + 7;
ll qpow(ll a, ll b){
ll ans = 1;
while (b) {
if (b & 1){
(ans *= a) %= mod;
}
(a *= a) %= mod;
b >>= 1;
}
return ans;
}
int n,m;
int a[limit];
void solve() {
cin>>n;
rep(i,1,n){
cin>>a[i];
}
int ans = 0;
int cur = a[1];
int num = 0; // how many segments with
rep(i,2,n){
if(!cur){
++ans;
cur = a[i];
}else{
cur &= a[i];
}
if(i == n and !cur)
++ans;
}
if (!ans)
++ans;
cout<<ans<<endl;
}
int32_t main() {
#ifdef LOCAL
FOPEN;
// FOUT;
#endif
FASTIO
int kase;
cin>>kase;
while (kase--)
invoke(solve);
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
return 0;
}
C. Vampiric Powers, anyone?
这题通过异或我们想到前缀和，然后数字还不大，所以我们只需要判断下后面能否从之前的前缀和里recover出来就好了
代码
#include <bits/stdc++.h>
using namespace std;
constexpr int limit = (2e5 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;
char s = getchar();
while (s > '9' || s < '0') {
if (s == '-')sign = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if (x / 10) print(x / 10);
*O++ = x % 10 + '0';
}
void write(ll x, char c = 't') {
if (x < 0)putchar('-'), x = -x;
print(x);
if (!isalpha(c))*O++ = c;
fwrite(obuf, O - obuf, 1, stdout);
O = obuf;
}
constexpr ll mod = 1e9 + 7;
ll qpow(ll a, ll b){
ll ans = 1;
while (b) {
if (b & 1){
(ans *= a) %= mod;
}
(a *= a) %= mod;
b >>= 1;
}
return ans;
}
int n,m;
int a[limit];
void solve() {
cin>>n;
int x = 0;
int ans = 0;
rep(i,1,n){
cin>>a[i];
ans = max(ans, a[i]);
}
map<int, int>mp;
per(i,1, n + 1){
x ^= a[i];
rep(j,0,1<<8){
if(mp[j]){
ans = max(1ll * ans, j ^ x);
}
}
mp[x]++;
}
cout<<ans<<endl;
}
int32_t main() {
#ifdef LOCAL
FOPEN;
// FOUT;
#endif
FASTIO
int kase;
cin>>kase;
while (kase--)
invoke(solve);
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
return 0;
}
D. Professor Higashikata
这题真是脑血栓题了，我一开始就想到首先我们需要找到拼成的string每个distinct id第一次出现的序列，按照出现的先后次序给每个id重新编号，当我们有n个bit为1的时候，如果要获取字典序最大的序列，我们需要把除了已经为1的前min(n, |拼接的string的distinct ids|)个非1bit变为1，那么怎么搞呢？我们自然可以用树状数组维护，那么有效的位置就是[1, min(|串中总公共的1的个数|, |拼接的string的distinct ids|)]
然后脑血栓的点来了，就是我没有非常handy的工具去快速记录l到r区间内没有被覆盖过的点，显然当l和r非常大的时候，暴力赋值nlogn是不可以的，后来我想到我们可以通过线段树 + 二分每次跳过已经被染色的段，这样的话总体复杂度是logn * logn的，然后还是不行，我吐了呀，按理说2e5是可以的
代码如下
代码
#include <bits/stdc++.h>
using namespace std;
constexpr int limit = (2e5 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;
char s = getchar();
while (s > '9' || s < '0') {
if (s == '-')sign = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if (x / 10) print(x / 10);
*O++ = x % 10 + '0';
}
void write(ll x, char c = 't') {
if (x < 0)putchar('-'), x = -x;
print(x);
if (!isalpha(c))*O++ = c;
fwrite(obuf, O - obuf, 1, stdout);
O = obuf;
}
int n;
int a[limit];
// seg tree with interval add
struct node{
int l,r;
ll sum,add;
}tr[limit<<2];
void pushup(int u){
tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}
void pushdown(int u){
if(tr[u].add){
tr[u<<1].add += tr[u].add;
tr[u<<1|1].add += tr[u].add;
tr[u<<1].sum += tr[u].add * (tr[u<<1].r - tr[u<<1].l + 1);
tr[u<<1|1].sum += tr[u].add * (tr[u<<1|1].r - tr[u<<1|1].l + 1);
tr[u].add = 0;
}
}
void build(int u, int l, int r){
tr[u] = {l,r,0,0};
if(l == r){
tr[u].sum = a[l];
return;
}
int mid = (l + r) >> 1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u, int l, int r, int val){
if(tr[u].l >= l && tr[u].r <= r){
tr[u].add += val;
tr[u].sum += val * (tr[u].r - tr[u].l + 1);
return;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid) modify(u<<1,l,r,val);
if(r > mid) modify(u<<1|1,l,r,val);
pushup(u);
}
ll query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r){
return tr[u].sum;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
ll ans = 0;
if(l <= mid) ans += query(u<<1,l,r);
if(r > mid) ans += query(u<<1|1,l,r);
return ans;
}
// 把区间所有的值变成1
void modify(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r){
tr[u].sum = tr[u].r - tr[u].l + 1;
tr[u].add = 1;
return;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid) modify(u<<1,l,r);
if(r > mid) modify(u<<1|1,l,r);
pushup(u);
}
// 给这个区间清零
void zero(int root, int l, int r){
if(tr[root].l >= l && tr[root].r <= r){
tr[root].sum = 0;
tr[root].add = 0;
return;
}
pushdown(root);
int mid = (tr[root].l + tr[root].r) >> 1;
if(l <= mid) zero(root<<1,l,r);
if(r > mid) zero(root<<1|1,l,r);
pushup(root);
}
int tree[limit];
void add(int pos, int val){
for(int i = pos; i <= n; i += lowbit(i)){
tree[i] += val;
}
}
ll query(int pos){
ll ans = 0;
for(int i = pos; i; i -= lowbit(i)){
ans += tree[i];
}
return ans;
}
void solve() {
cin>>n;
int m,k;
cin>>m>>k;
string str;
cin>>str;
str = " " + str;
build(1, 1, n); // build tree
set<int>s;
auto get_pos = [&](int now, int pos) -> int {
if(now + 1 <= pos and !s.contains(now + 1)){
return now + 1;
}
int ans = now;
for(int l = now, r = pos; l <= r; ){
auto mid = l + (r - l) / 2;
if(query(1, now, mid) < mid - now + 1){
l = mid + 1;
}else{
ans = mid;
r = mid - 1;
}
}
if(ans == now){
ans++;
}
return ans;
};
map<int, int>ids;
int tot = 0;
rep(i, 1, m){
int l,r;
cin>>l>>r;
// cout<<"here "<<l<<" "<<r<<endl;
for(int now = l; now <= r; now = get_pos(now, r)){
// if(l == 6 and r == 8){
// cout<<now<<"ok"<<endl;
// }
if(s.contains(now))
continue;
ids[now] = ++tot;
s.insert(now);
}
zero(1, l, r); //dynamic zeroing
modify(1, l, r, 1);
// cout<<"one"<<endl;
}
// for(auto [kk, v]: ids){
// cout<<kk<<" "<<v<<endl;
// }
int cnt = count(str.begin(), str.end(), '1');
rep(i,1,n){
if(s.contains(i))add(ids[i], str[i] == '1');
}
int cur = tot;
rep(i,1,k){
int x;
cin>>x;
str[x] = str[x] == '1' ? '0' : '1';
if(str[x] == '0'){
cnt--;
if(ids.contains(x)) {
add(ids[x], -1);
}
}else{
cnt++;
if(ids.contains(x)) {
add(ids[x], 1);
}
}
cout<<min(cnt, tot) - query(min(cnt, tot))<<endl;
}
}
int32_t main() {
#ifdef LOCAL
FOPEN;
// FOUT;
#endif
FASTIO
// int kase;
// cin>>kase;
// while (kase--)
invoke(solve);
// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
return 0;
}