emancipation

1720

acwing_74240

Mycraft
qwerxyz

slight
Luo_gu_ykc
OI
DPH
ZDC
leisure
zhuxiaorui
ya鹏鹏

emancipation
9小时前
#include<iostream>
#include<queue>
#include<cstring>
#define ios ios::sync_with_stdio(false),cin.tie(NULL)
#define lc k<<1
#define rc k<<1|1

using namespace std;
const int N = 5000010;
int n,m;
struct node{
int l,r;
int sum;
int mx;
int lmx;
int rmx;
}tr[N*4];
int a[N];

void pushup(int k){
tr[k].mx = max(max(tr[lc].mx,tr[rc].mx),tr[lc].rmx+tr[rc].lmx);
tr[k].sum = tr[lc].sum+tr[rc].sum;
tr[k].lmx = max(tr[lc].lmx,tr[lc].sum+tr[rc].lmx);
tr[k].rmx = max(tr[rc].rmx,tr[rc].sum+tr[lc].rmx);
}

void build(int k,int l,int r){
tr[k] = {l,r};
if(l == r) {
tr[k] = {l,r,a[l],a[l],a[l],a[l]};
return;
}
int m = l+r>>1;
build(lc,l,m);
build(rc,m+1,r);
pushup(k);
}

void update(int k,int x,int v){
if(tr[k].l == x && tr[k].r == x){
tr[k] = {x,x,v,v,v,v};
return;
}
int m = tr[k].l+tr[k].r>>1;
if(x<=m) update(lc,x,v);
else update(rc,x,v);
pushup(k);
}

node query(int k,int l,int r){
if(tr[k].l>=l&&tr[k].r<=r)return tr[k];
int m = tr[k].l+tr[k].r>>1;
if(r<=m) return query(lc,l,r);
else if(l>m) return query(rc,l,r);
else {
auto left = query(lc,l,m);
auto right = query(rc,m+1,r);
node ans;
ans.l = l,ans.r = r,ans.sum = left.sum+right.sum;
ans.mx = max(max(left.mx,right.mx),left.rmx+right.lmx);
ans.lmx = max(left.lmx,left.sum+right.lmx);
ans.rmx = max(right.rmx,right.sum+left.rmx);
return ans;
}
}

int main(){
ios;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
while(m--){
int op,x,y;
cin>>op>>x>>y;
if(op == 1){
if(x>y)swap(x,y);
cout<<query(1,x,y).mx<<"\n";
}
else update(1,x,y);
}
return 0;
}


emancipation
14小时前
#pragma GCC optimize(2)

#include<iostream>
#include<queue>
#include<cstring>
#define ios ios::sync_with_stdio(false),cin.tie(NULL)
#define lc k<<1
#define rc k<<1|1
#define int long long
using namespace std;
const int N = 2e5+10;
int m,p;

struct node{
int l,r;
int mx;
}tr[N*4];
int a,cnt;

void pushup(int k){
tr[k].mx = max(tr[lc].mx,tr[rc].mx);
}

void build(int k,int l,int r){
tr[k] = {l,r,0};
if(l == r) return;
int m = l+r>>1;
build(lc,l,m);
build(rc,m+1,r);
pushup(k);
}

void update(int k, int x, int p) {
if (tr[k].l == x && tr[k].r == x) {
tr[k].mx += p;
return;
}
int m = tr[k].l + tr[k].r >> 1;
if (x <= m)update(lc, x, p);
if (x > m)update(rc, x, p);
pushup(k);
}

int query(int k, int l,int r) {
if (tr[k].l >= l && tr[k].r <= r)
return tr[k].mx;
int m = tr[k].l + tr[k].r >> 1;
int ans = 1<<63;
if (l <= m)ans = max(ans, query(lc, l, r));
if (r > m)ans = max(ans, query(rc, l, r));
return ans;
}

signed main(){
ios;
cin>>m>>p;
build(1,1,N);
while(m--){
char op;
int t;
cin>>op>>t;
if(op == 'A')
update(1,++cnt,(t+a)%p);
else{
a = query(1,cnt-t+1,cnt);
cout<<a<<endl;
}
}
return 0;
}


emancipation
14小时前

//#pragma GCC optimize(2)

#include<iostream>
#include<queue>
#include<cstring>
#define ios ios::sync_with_stdio(false),cin.tie(NULL)
#define lc k<<1
#define rc k<<1|1
#define int long long
using namespace std;
const int N = 2e5+10;
int m,p;

struct node{
int l,r;
int mx;
}tr[N*4];
int a,cnt;

void pushup(int k){
tr[k].mx = max(tr[lc].mx,tr[rc].mx);
}

void build(int k,int l,int r){
tr[k] = {l,r,0};
if(l == r) return;
int m = l+r>>1;
build(lc,l,m);
build(rc,m+1,r);
pushup(k);
}

void update(int k, int x, int p) {
if (tr[k].l == x && tr[k].r == x) {
tr[k].mx += p;
return;
}
int m = tr[k].l + tr[k].r >> 1;
if (x <= m)update(lc, x, p);
if (x > m)update(rc, x, p);
pushup(k);
}

int query(int k, int l,int r) {
if (tr[k].l >= l && tr[k].r <= r)
return tr[k].mx;
int m = tr[k].l + tr[k].r >> 1;
int ans = 1<<63;
if (l <= m)ans = max(ans, query(lc, l, r));
if (r > m)ans = max(ans, query(rc, l, r));
return ans;
}

signed main(){
ios;
cin>>m>>p;
build(1,1,N);
while(m--){
char op;
int t;
cin>>op>>t;
if(op == 'A')
update(1,++cnt,(t+a)%p);
else{
a = query(1,cnt-t+1,cnt);
cout<<a<<endl;
}
}
return 0;
}


emancipation
15小时前
#include<iostream>

using namespace std;
const int N = 1e6+10;
int n;
char s[N];
int id[N],cnt[N],idx;
int tr[N][26];
int q[N];
int fail[N];

void insert(int i){
int p=0;
for(int i=0;s[i];i++){
int u =s[i]-'a';
if(!tr[p][u])tr[p][u] = ++idx;
p = tr[p][u];
cnt[p]++;
}
id[i] = p;
}

void build(){
int h,t;
h=1,t=0;
for(int i=0;i<26;i++){
if(tr[0][i])
q[++t] = tr[0][i];
}

while(h<=t){
int u = q[h++];
for(int i=0;i<26;i++){
int v = tr[u][i];
if(v) fail[v] = tr[fail[u]][i],q[++t] = v;
else tr[u][i] = tr[fail[u]][i];
}
}
}

int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s;
insert(i);
}

build();
for(int i=idx;i>=1;i--){
cnt[fail[q[i]]] += cnt[q[i]];
}
for(int i=1;i<=n;i++)
cout<<cnt[id[i]]<<"\n";
return 0;
}


emancipation
22小时前
#include<iostream>
#include<queue>
#include<cstring>
#define ios ios::sync_with_stdio(false),cin.tie(NULL)

using namespace std;
const int N = 6e5+10;
int T;
int n,m;
const int len = 25;
int ch[N*len][2],x;
int root[N],s[N],idx,ver[N*len];

void insert(int x,int y,int i){
ver[x] = i;
for(int k=len;k>=0;k--){
int c = s[i]>>k&1;
ch[x][!c] = ch[y][!c];
ch[x][c] = ++idx;
x = ch[x][c],y = ch[y][c];
ver[x] = i;
}
}

int query(int x,int l,int v){
int res = 0;
for(int k=len;k>=0;k--){
int c = v>>k&1;
if(ver[ch[x][!c]]>=l)
x = ch[x][!c],res+=1<<k;
else x = ch[x][c];
}
return res;
}

int main(){
ios;cin>>n>>m;
ver[0] = -1;
root[0] = ++idx;
insert(root[0],0,0);
for(int i=1;i<=n;i++){
cin>>x;
s[i] = s[i-1]^x;
root[i] = ++idx;
insert(root[i],root[i-1],i);
}

for(int j=1,i=n;j<=m;j++){
char op;
int l,r;
cin>>op;
if(op == 'A'){
i++;
cin>>x;
root[i] = ++idx;
s[i] = s[i-1]^x;
insert(root[i],root[i-1],i);
}
else{
cin>>l>>r>>x;
cout<<query(root[r-1],l-1,s[i]^x)<<"\n";
}
}
return 0;
}



emancipation
22小时前

a[1] xor a[2] xor a[3] xor…xor a[p-2] xor a[p-1] xor a[p] xor…xor a[n]

s[p] = a[1] xor a[2] xor a[3] xor…xor a[p-2] xor a[p-1] xor a[p]

ans = a[p] xor a[p+1]… xor a[n] = s[p-1] xor s[n]^x

L<=P<=R => L-1<=P-1<=R-1

#include<iostream>
#include<queue>
#include<cstring>
#define ios ios::sync_with_stdio(false),cin.tie(NULL)

using namespace std;
const int N = 6e5+10;
int T;
int n,m;
const int len = 25;
int ch[N*len][2],x;
int root[N],s[N],idx,ver[N*len];

void insert(int x,int y,int i){
ver[x] = i;
for(int k=len;k>=0;k--){
int c = s[i]>>k&1;
ch[x][!c] = ch[y][!c];
ch[x][c] = ++idx;
x = ch[x][c],y = ch[y][c];
ver[x] = i;
}
}

int query(int x,int l,int v){
int res = 0;
for(int k=len;k>=0;k--){
int c = v>>k&1;
if(ver[ch[x][!c]]>=l)
x = ch[x][!c],res+=1<<k;
else x = ch[x][c];
}
return res;
}

int main(){
ios;cin>>n>>m;
ver[0] = -1;
root[0] = ++idx;
insert(root[0],0,0);
for(int i=1;i<=n;i++){
cin>>x;
s[i] = s[i-1]^x;
root[i] = ++idx;
insert(root[i],root[i-1],i);
}

for(int j=1,i=n;j<=m;j++){
char op;
int l,r;
cin>>op;
if(op == 'A'){
i++;
cin>>x;
root[i] = ++idx;
s[i] = s[i-1]^x;
insert(root[i],root[i-1],i);
}
else{
cin>>l>>r>>x;
cout<<query(root[r-1],l-1,s[i]^x)<<"\n";
}
}
return 0;
}



splay

#include<iostream>
#include<queue>
#include<cstring>
#define ios ios::sync_with_stdio(false),cin.tie(nullptr)
using namespace std;
const int N = 100010 ;

struct node{
int s[2];
int p;
int v;
int cnt;
int size;
void init(int p1,int v1){
p = p1,v = v1;
cnt = size = 1;
}
}tr[N];
int root,idx;

void pushup(int x){
tr[x].size = tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+tr[x].cnt;
}

void rotate(int x){
int y = tr[x].p,z = tr[y].p;
int k = tr[y].s[1] == x;
tr[y].s[k] = tr[x].s[k^1];
tr[tr[x].s[k^1]].p = y;
tr[x].s[k^1] = y;
tr[y].p = x;
tr[z].s[tr[z].s[1] == y] = x;
tr[x].p = z;
pushup(y),pushup(x);
}

void splay(int x,int k){
while(tr[x].p != k){
int y = tr[x].p,z = tr[y].p;
if(z!=k)
(tr[y].s[0] == x)^(tr[z].s[0] == y)?rotate(x):rotate(y);
rotate(x);
}
if(k == 0)root = x;
}

void find(int v){
int x = root;
while(tr[x].s[v>tr[x].v] && v!=tr[x].v)
x = tr[x].s[v>tr[x].v];
splay(x,0);
}

int get_pre(int v){
find(v);
int x = root;
if(tr[x].v<v)return x;
x = tr[x].s[0];
while(tr[x].s[1])
x = tr[x].s[1];
return x;
}

int get_suf(int v){
find(v);
int x = root;
if(tr[x].v>v)return x;
x = tr[x].s[1];
while(tr[x].s[0])
x = tr[x].s[0];
return x;
}

void del(int v){
int pre = get_pre(v);
int suf = get_suf(v);
splay(pre,0),splay(suf,pre);
int del = tr[suf].s[0];
if(tr[del].cnt>1)
tr[del].cnt--,splay(del,0);
else tr[suf].s[0] = 0,splay(suf,0);
}

int get_rank(int v){
find(v);
return tr[tr[root].s[0]].size;
}

int get_val(int k){
int x = root;
while(1){
int y = tr[x].s[0];
if(tr[y].size+tr[x].cnt<k){
k-=tr[y].size+tr[x].cnt;
x = tr[x].s[1];
}
else{
if(tr[y].size>=k)x = tr[x].s[0];
else break;
}
}
splay(x,0);
return tr[x].v;
}

void insert(int v){
int x = root,p=0;
while(x&&tr[x].v!=v)
p = x,x=tr[x].s[v>tr[x].v];
if(x)tr[x].cnt++;
else{
x=++idx;
tr[p].s[v>tr[p].v] = x;
tr[x].init(p,v);
}
splay(x,0);
}

int n;
int main(){
ios;
insert(-1e9),insert(1e9);
cin>>n;
while(n--){
int op,x;
cin>>op>>x;
if(op == 1)insert(x);
if(op == 2)del(x);
if(op == 3)cout<<get_rank(x)<<'\n';
if(op == 4)cout<<get_val(x+1)<<'\n';
if(op == 5)cout<<tr[get_pre(x)].v<<'\n';
if(op == 6)cout<<tr[get_suf(x)].v<<'\n';
}
return 0;
}



#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;

unordered_map <string, int> d;
queue<string> q;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
string end = "12345678x";

void bfs(string str) {
q.push(str);
string end = "12345678x";
d[str] = 0;
while (q.size()) {
auto s = q.front(); q.pop();
if (s == end)return;
int k = s.find('x');
int x = k / 3, y = k % 3;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
int dist = d[s];
swap(s[k], s[nx * 3 + ny]);
if (!d.count(s))d[s] = dist + 1, q.push(s);
swap(s[k], s[nx * 3 + ny]);
}
}
}
}

int main()
{
string s;
char ch;
while (cin >> ch) {
s += ch;
}
bfs(s);
if (!d.count("12345678x"))cout << -1;
else cout << d["12345678x"];
return 0;
}


#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 10;
int n;
vector<int> v[100];

int col[N*2],p[N*2],q[N*2];
int path[N*2];
int cnt;
void dfs(int i){
if(i>8){
cnt++;
for(int i=1;i<=8;i++)
v[cnt].push_back(path[i]);
return;
}
for(int j=1;j<=8;j++){
if(col[j]||p[i+j]||q[i-j+8])continue;
path[i] = j;
col[j] = p[i+j] = q[i-j+8] = 1;
dfs(i+1);
col[j] = p[i+j] = q[i-j+8] = 0;
}
}

int main(){
dfs(1);
cin>>n;
while(n--){
int x;
cin>>x;
for(int i:v[x])
cout<<i;
cout<<endl;
}
return 0;
}


#include<iostream>
#include<vector>
using namespace std;
const int N = 10010;
int a[N];
vector<int> e[N];
bool dg[N];
int dp[N][2];

void dfs(int u){
dp[u][0] = 0;
dp[u][1] = a[u];
for(int v:e[u]){
dfs(v);
dp[u][0]+=max(dp[v][0],dp[v][1]);
dp[u][1]+=dp[v][0];
}
}

int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=0;i<n-1;i++){
int l,k;
cin>>l>>k;
e[k].push_back(l);
dg[l] = true;
}
int root;
for(int i=1;i<=n;i++)
if(!dg[i])
root=i;
dfs(root);
cout<<max(dp[root][0],dp[root][1]);
}