头像

emancipation




离线:9小时前


最近来访(18)
用户头像
acwing_74240
用户头像
棒子面白周
用户头像
第一万零一次AC
用户头像
Mycraft
用户头像
qwerxyz
用户头像
该训练了
用户头像
今天你爆int了吗
用户头像
青森.
用户头像
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;
}


活动打卡代码 AcWing 1275. 最大数

emancipation
14小时前

题解详见
https://www.acwing.com/solution/content/133376/

#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小时前

模板稍加变形
利用线段树记录区间最大值

先构建空树
插入值时做修改
区间查询 [n-L+1 ,n]

//#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;
}


活动打卡代码 AcWing 256. 最大异或和

emancipation
22小时前

题解链接:
https://www.acwing.com/solution/content/133274/

#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

设 v = s[n]^x => ans = s[p-1] xor v

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

记录每个版本的tire 在[L-1,R-1]的区间反向查找v,并记录数值。

#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]);
}