# Solution for CEOI2022()-其他

## Solution for CEOI2022()

### Description

$$N\leqslant 2\cdot 10^5,Q\leqslant 10^6,0\leqslant t\leqslant 10^9$$.

### Code

.1a
.2b
freopen()
# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while(!isdigit(s=getchar())) f|=(s=='-');
for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
return f? -x: x;
}
template <class T>
inline void write(T x) {
static int writ[50], w_tp=0;
if(x<0) putchar('-'), x=-x;
do writ[++w_tp]=x-x/10*10, x/=10; while(x);
while(putchar(writ[w_tp--]^48), w_tp);
}

# include <vector>
# include <iostream>
using namespace std;
typedef pair <int,int> par;

const int MAXN = 2e5+5;
const int MAXM = 1e6+5;

vector <par> q[MAXN]; int ans[MAXM];
int n, Q, a[MAXN], stk[MAXN], tp, nxt[MAXN], pos[MAXN];

namespace fwt {
int c[MAXN];
int lowbit(int x) { return x&-x; }
while(x<=n) c[x]+=k, x+=lowbit(x);
}
for(; x; x-=lowbit(x)) r+=c[x]; return r;
}
int kth(int& k,int r=0) {
for(int i=17; i>=0; --i)
if(r+(1<<i)<=n && c[r+(1<<i)]<k)
k -= c[r=r+(1<<i)]; return r+1;
}
}

int main() {
for(int i=n; i; --i) {
while(tp && a[i]>a[stk[tp]]) --tp;
if(tp) nxt[i] = stk[tp];
else nxt[i] = n+1; stk[++tp]=i;
}
for(int i=1;i<=Q;++i) {
q[t].emplace_back(make_pair(x,i));
}
for(int t=0; t<=n; ++t) {
for(auto& i:q[t]) {
} int mid = (n>>1)+1, lead = fwt::kth(mid);
if(mid==1) continue;
}
for(int i=1;i<=Q;++i) print(ans[i],'\n');
return 0;
}


### Description

$$N\leqslant 10^6$$.

### Code

# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while(!isdigit(s=getchar())) f|=(s=='-');
for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
return f? -x: x;
}
template <class T>
inline void write(T x) {
static int writ[50], w_tp=0;
if(x<0) putchar('-'), x=-x;
do writ[++w_tp]=x-x/10*10, x/=10; while(x);
while(putchar(writ[w_tp--]^48), w_tp);
}

# include <cstring>
# include <iostream>
using namespace std;

const int MAXN = 7e6+5;

char s[MAXN]; bool d[MAXN]; int dp[MAXN][2];
int len, stk[MAXN], tp, son[MAXN][2], n;

void dfs(int u) {
if(!son[u][0]) return; dp[u][d[u]^1]=0;
for(int i=0, v=son[u][i]; i<2; v=son[u][++i]) {
dfs(v); dp[u][d[u]^1] += dp[v][d[u]^1];
dp[u][d[u]] = min(dp[u][d[u]], dp[v][d[u]]);
}
}

int main() {
scanf("%s",s+1), len=strlen(s+1);
for(int i=1; i<=len; ++i) {
if(s[i]=='m') stk[++tp]=++n,
d[n] = (s[i+1]=='i'?0:1), i+=3;
else if(s[i]==')') son[stk[tp-1]][1]=stk[tp], --tp;
else if(s[i]==',') son[stk[tp-1]][0]=stk[tp], --tp;
else stk[++tp]=++n;
} int all=0;
for(int i=1;i<=n;++i)
if(son[i][0]) dp[i][0]=dp[i][1]=n+1;
else dp[i][0]=dp[i][1]=1, ++ all;
dfs(1); print(all-dp[1][0]-dp[1][1]+2,'\n');
return 0;
}


### Description

? a b

$$N\leqslant 10^6,Q=K-1,0<w_i\leqslant 2000,2\leqslant K\leqslant 10^5,T\leqslant \min\{K^2,10^5\}$$.

### Code

为什么明知道没有代码你还要点开呢？

————————

### Description

$$N\leqslant 2\cdot 10^5,Q\leqslant 10^6,0\leqslant t\leqslant 10^9$$.

### Code

.1a
.2b
freopen()
# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while(!isdigit(s=getchar())) f|=(s=='-');
for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
return f? -x: x;
}
template <class T>
inline void write(T x) {
static int writ[50], w_tp=0;
if(x<0) putchar('-'), x=-x;
do writ[++w_tp]=x-x/10*10, x/=10; while(x);
while(putchar(writ[w_tp--]^48), w_tp);
}

# include <vector>
# include <iostream>
using namespace std;
typedef pair <int,int> par;

const int MAXN = 2e5+5;
const int MAXM = 1e6+5;

vector <par> q[MAXN]; int ans[MAXM];
int n, Q, a[MAXN], stk[MAXN], tp, nxt[MAXN], pos[MAXN];

namespace fwt {
int c[MAXN];
int lowbit(int x) { return x&-x; }
while(x<=n) c[x]+=k, x+=lowbit(x);
}
for(; x; x-=lowbit(x)) r+=c[x]; return r;
}
int kth(int& k,int r=0) {
for(int i=17; i>=0; --i)
if(r+(1<<i)<=n && c[r+(1<<i)]<k)
k -= c[r=r+(1<<i)]; return r+1;
}
}

int main() {
for(int i=n; i; --i) {
while(tp && a[i]>a[stk[tp]]) --tp;
if(tp) nxt[i] = stk[tp];
else nxt[i] = n+1; stk[++tp]=i;
}
for(int i=1;i<=Q;++i) {
q[t].emplace_back(make_pair(x,i));
}
for(int t=0; t<=n; ++t) {
for(auto& i:q[t]) {
} int mid = (n>>1)+1, lead = fwt::kth(mid);
if(mid==1) continue;
}
for(int i=1;i<=Q;++i) print(ans[i],'\n');
return 0;
}


### Description

$$N\leqslant 10^6$$.

### Code

# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while(!isdigit(s=getchar())) f|=(s=='-');
for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
return f? -x: x;
}
template <class T>
inline void write(T x) {
static int writ[50], w_tp=0;
if(x<0) putchar('-'), x=-x;
do writ[++w_tp]=x-x/10*10, x/=10; while(x);
while(putchar(writ[w_tp--]^48), w_tp);
}

# include <cstring>
# include <iostream>
using namespace std;

const int MAXN = 7e6+5;

char s[MAXN]; bool d[MAXN]; int dp[MAXN][2];
int len, stk[MAXN], tp, son[MAXN][2], n;

void dfs(int u) {
if(!son[u][0]) return; dp[u][d[u]^1]=0;
for(int i=0, v=son[u][i]; i<2; v=son[u][++i]) {
dfs(v); dp[u][d[u]^1] += dp[v][d[u]^1];
dp[u][d[u]] = min(dp[u][d[u]], dp[v][d[u]]);
}
}

int main() {
scanf("%s",s+1), len=strlen(s+1);
for(int i=1; i<=len; ++i) {
if(s[i]=='m') stk[++tp]=++n,
d[n] = (s[i+1]=='i'?0:1), i+=3;
else if(s[i]==')') son[stk[tp-1]][1]=stk[tp], --tp;
else if(s[i]==',') son[stk[tp-1]][0]=stk[tp], --tp;
else stk[++tp]=++n;
} int all=0;
for(int i=1;i<=n;++i)
if(son[i][0]) dp[i][0]=dp[i][1]=n+1;
else dp[i][0]=dp[i][1]=1, ++ all;
dfs(1); print(all-dp[1][0]-dp[1][1]+2,'\n');
return 0;
}


### Description

? a b

$$N\leqslant 10^6,Q=K-1,0<w_i\leqslant 2000,2\leqslant K\leqslant 10^5,T\leqslant \min\{K^2,10^5\}$$.

### Code

为什么明知道没有代码你还要点开呢？