2024icpc杭州区域赛（A，K，E，H，M，B）

题目链接:Dashboard - The 2024 ICPC Asia Hangzhou Regional Contest (The 3rd Universal Cup. Stage 25: Hangzhou) - Codeforces

A. AUS

前置知识点：并查集

思路

题意就是将字符串S1与S2相同位置上的字符转换为同一个字符，然后检查S3按照S1与S2的映射方法是否和S1与S2映射出来的是否字符串不同

首先可以根据S1，S2，S3的字符串的长度来提前进行判断

然后将S1与S2相同位置的字符加入并查集，之后判断S3的每个位置

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

struct DSU {
    vector<int>p,siz;
    DSU(int n):p(n),siz(n,1) {
        iota(p.begin(),p.end(),0);
    }
    int find(int x) {
        while(x!=p[x]) x=p[x]=p[p[x]];
        return x;
    }
    bool same(int x,int y) {
        return find(x)==find(y);
    }
    bool merge(int x, int y) {
        x=find(x),y=find(y);
        if (x==y) return false;
        siz[x]+=siz[y],p[y]=x;
        return true;
    }
    int size(int x) {
        return siz[find(x)];
    }
};

void solve(){
    string a,b,c;
    cin>>a>>b>>c;
    DSU dsu(27);
    int la=a.size();
    int lb=b.size();
    int lc=c.size();
    if(la!=lb){
        cout<<"NO\n";return;
    }
    if(la!=lc){
        cout<<"YES\n";return;
    }
    for(int i=0;i<la;i++){
        dsu.merge(a[i]-'a',b[i]-'a');
    }

    for(int i=0;i<la;i++){
        if(dsu.find(a[i]-'a')!=dsu.find(c[i]-'a')){
            cout<<"YES\n"; return;
        }
    }
    cout<<"NO\n";

}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

K. Kind of Bingo

前置知识点：二分答案

思路

题意能够很容易地看出用二分来解决，当然可以参考官方题解不用二分的做法

我们需要从1-n*m对p[i]进行操作，每次我们会对第行进行标记，直到标记完一整行，我们的k次操作可以将某一行提前标记k个

对于check函数，我们假设当前操作x次，从1--x遍历p[i]，统计每一行被标记的数量，如果最大的标记数量+k>=n，那么x是足够的

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    vi p(n*m+10);
    for(int i=1;i<=n*m;i++){
        cin>>p[i];
    }

    int l=m,r=n*m;
    int ans=0;
    
    auto check=[&](int x)->bool{
        vi h(n);
        for(int i=1;i<=x;i++){
            if(p[i]%m==0){
                h[p[i]/m-1]++;
            }else{
                h[p[i]/m]++;
            }
        }
        int mx=0;
        for(int i=0;i<n;i++){
            mx=max(mx,h[i]);
        }
        if(mx+k>=m) return true;
        else return false;
    };

    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    cout<<ans<<"\n";
}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

E. Elevator II

前置知识点：贪心+模拟

思路

因为电梯向下走是不消耗电能的，而且每次只能装一个人，所以对于每个人来说我们都不可避免的消耗r-l个电能，我们可以贪心地将电梯送到最上面，然后再按照r从大到小依次将人送到目的地

对于从电梯送到最上面的过程，因为电梯向下走是不消耗电能的，所以我们会把能捎上的人都给捎上，用now表示电梯当前的层数，只要l<=now且r>=now的我们就可以提前将此人送到目的地

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

struct node{
    int l,r,id;
};
bool cmpl(node x,node y){
    if(x.l==y.l){
        return x.r>y.r;
    }
    return x.l<y.l;
}
bool cmpr(node x,node y){
    return x.r>y.r;
}

void solve(){
    int n,f;
    cin>>n>>f;
    node v[n+10];
    for(int i=1;i<=n;i++){
        cin>>v[i].l>>v[i].r;
        v[i].id=i;
    }
    map<int,bool> mp;   //用来统计已经送走人的编号
    sort(v+1,v+1+n,cmpl);
    
    int now=f;
    int ans=0;
    vi res;

    for(int i=1;i<=n;i++){
        int l=v[i].l,r=v[i].r;
        if(l<=now){
            if(r>now){
                ans+=(r-l);
                now=r;
                mp[v[i].id]=true;
                res.push_back(v[i].id);
            }
        }else{
            ans+=(l-now);
            ans+=(r-l);
            now=r;
            mp[v[i].id]=true;
            res.push_back(v[i].id);
        }
    }
    sort(v+1,v+1+n,cmpr);

    for(int i=1;i<=n;i++){
        int l=v[i].l,r=v[i].r;
        if(!mp[v[i].id]){
            ans+=(r-l);
            res.push_back(v[i].id);
        }
    }
    cout<<ans<<"\n";
    for(int x:res){
        cout<<x<<" ";
    }
    cout<<"\n";
}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

H. Heavy-light Decomposition

前置知识点：树链剖分(了解基础即可)

思路

首先当最长的链只有一条时，我们可以将此链的开头当作根节点，其他链都以根节点为开头即可

最长链有多条时，我们可以将尝试将某条最长链的开头当根节点，然后将最长链的第二个节点当作最短链的开头，这样便能保证我们将其他链以根节点作为开头，也会将这条最长链为重链，此处我们得保证最短链的长度<=最长链的长度-2

综上，在最长链的数量>1时且最短链的长度>最长链的长度-2时输出IMPOSSIBLE，其余情况按上面构造即可

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

void solve(){
    int n,k;
    cin>>n>>k;
    vi p(n+10);
    vi l(k+1),r(k+1);
    int mx=0;
    int mi=inf;
    map<int,int>mp;
    int idmx=0;
    int idmi=0;

    for(int i=1;i<=k;i++){
        cin>>l[i]>>r[i];
        if(mx<r[i]-l[i]){
            idmx=i;
            mx=r[i]-l[i];
        }
        if(mi>r[i]-l[i]){
            idmi=i;
            mi=r[i]-l[i];
        }
        mp[r[i]-l[i]]++;
    }
    if(mp[mx]>1&&mi>mx-2){
        cout<<"IMPOSSIBLE\n";return;
    }
    if(mp[mx]>1){
        for(int i=1;i<=k;i++){
            if(i==idmx) p[l[i]]=0;
            else if(i==idmi){
                p[l[i]]=l[idmx]+1;
            }else{
                p[l[i]]=l[idmx];
            }
            for(int j=l[i]+1;j<=r[i];j++){
                p[j]=j-1;
            }
        }
    }else{
        for(int i=1;i<=k;i++){
            if(i==idmx) p[l[i]]=0;
            else{
                p[l[i]]=l[idmx];
            }
            for(int j=l[i]+1;j<=r[i];j++){
                p[j]=j-1;
            }
        }
    }
    
    for(int i=1;i<=n;i++){
        cout<<p[i]<<" ";
    }cout<<"\n";
}

signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

M. Make It Divisible

前置知识点：笛卡尔树

思路

首先对于[l,r]区间内的数能被其中的某个数整除，那么这个数一定是其最小值，题目是[1,n]中的所有[l,r]区间都是整除区间，我们需要维护区间最小值以及各个区间还得按顺序，这时候我们就能够发现用笛卡尔树建立正好，按小根堆的方式构建

对于每个x值我们从顶部向下看是否能整除，那么此时我们需要遍历O(k*n)，显然复杂度很高，那么我们需要考虑如果简化缩减x的值

此处还有一个精妙的结论，是的一个因数，其中我们对a+x并不会改变的值，因此我们只需要遍历检查一下的因数即可

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

int n,m;
vi a(N);
vi b(N);

//构建笛卡尔树
vi ls(N),rs(N),sta(N);
void build(){
    int top=0;
    for(int i=1;i<=n;i++){
        int pos=top;
        while(pos>0 && b[sta[pos]]>b[i]){
            pos--;
        }
        if(pos>0){
            rs[sta[pos]] = i;
        }
        if(pos<top){
            ls[i]=sta[pos+1];
        }
        sta[++pos] =i;
        top=pos;
    }
}

bool dfs(int l,int r,int x,int fa){
    if(fa && b[x]%b[fa]) return 0;
    if(l>=r) return 1;
    return dfs(l,x-1,ls[x],x)&&dfs(x+1,r,rs[x],x);
}

bool check(int x){
    
    for(int i=1;i<=n;i++) b[i]=a[i]+x;
    for(int i=1;i<=n;i++) ls[i]=rs[i]=0;    //重置笛卡尔树
    build();

    return dfs(1,n,sta[1],0);
    
}

void solve(){

    cin>>n>>m;
    
    int mn=inf;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mn=min(mn,a[i]);
    }
    
    int g=0;
    for(int i=1;i<n;i++){g=__gcd(g,abs(a[i]-a[i+1]));}  //求最大公约数做差之后即使+x最大公约数也不会受到影响

    if(g==0){   //只有一个数以及所有数都相等的情况
        cout<<m<<" "<<m*(m+1)/2<<"\n";return;
    }

    vi d;   //统计因子
    
    d.push_back(0);     //我习惯从下标1开始

    for(int i=1;i*i<=g;i++){    //求最大公约数的因子
        if(g%i==0){
            d.push_back(i);
            if(i*i!=g) d.push_back(g/i);
        }
    }
    int id=d.size()-1;


    int cnt=0,sum=0;
    for(int t=1;t<=id;t++){     //检查所有合法的因子
        int x=d[t]-mn;
        if(x<1 || x>m) continue;
        int ret=check(x);
        if(ret) cnt++,sum+=x;
    }

    cout<<cnt<<" "<<sum<<"\n";

}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

B. Barkley III

前置知识点：线段树+位运算

思路

本题很容易便能看出是个线段树的题，其中前两个操作是线段树的基础操作区间查询和单点修改，主要是实现第三个操作，我们需要额外维护一个在区间[l,r]内所有数按位与之后某位只有一个0参与&运算，我们只需移除这个数就能使得此区间内数&之后此位置的0变成1进而使得数变大

我们考虑这样一个数f，二进制下1表示该区间的数&之后此位置只有一个0参与&运算。

用表示[l,r]区间的&和

在l==r的情况下，对arr[i]取反即可

在向上传递的过程中

（左孩子的g值&右孩子的f值）|（右孩子的g值&左孩子的f值）这样便能将f重新统计更新

之后操作3便是先找到此区间内f值的最高位1，然后从线段树中找到此位置上为0的arr[i]删除即可

代码 

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=1e6+10;
const int inf=1e18;
const int mod=998244353;
const int mask=(~0ll);


vector<int> arr(N);
struct SegmentTree{
    vector<int> g,tag,f;
    SegmentTree(int n):g(4*n,0),tag(4*n,-1),f(4*n,0){}
    void up(int i){
        g[i] = g[i << 1] & g[i << 1 | 1];
        f[i] = (g[i << 1] & f[i << 1 | 1]) | (g[i << 1 | 1] & f[i << 1]);
    }
    
    void lazy(int i, int v, int n){
        g[i] &= v;
        int t = (~v) & ((n == 1) ? ~0ULL : 0);
        f[i] = (f[i] & v) | t;
        tag[i] &= v;
    }
    void down(int i, int ln, int rn){
        if(tag[i] != mask){
            lazy(i << 1, tag[i], ln);
            lazy(i << 1 | 1, tag[i], rn);
            tag[i] = mask;
        }
    }
    void build(int l, int r, int i){
        if(l == r){
            g[i] = arr[l];
            f[i] = (~arr[l]) & (mask);
        }else{
            int mid = (l + r) >> 1;
            build(l, mid, i << 1);
            build(mid + 1, r, i << 1 | 1);
            up(i);
        }
        tag[i] = mask;
    }
    void add(int jobl, int jobr, int jobv, int l, int r, int i){
        if(jobl <= l && r <= jobr){
            lazy(i, jobv, r - l + 1);
        }else{
            int mid = (l + r) >> 1;
            down(i, mid - l + 1, r - mid);
            if(jobl <= mid){
                add(jobl, jobr, jobv, l, mid, i << 1);
            }
            if(jobr > mid){
                add(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);
            }
            up(i);
        }
    }

    void updata(int s,int x,int l,int r,int i){
        
        if(l==r){
            g[i] = x;
            f[i] = (~x)&mask;
        }else{
            int mid = (l + r) >> 1;
            down(i,mid-l+1,r-mid);
            if(s<=mid){
                updata(s,x,l,mid,i << 1);
            }else{
                updata(s,x,mid+1,r,i<<1|1);
            }
            up(i);
        }

    }

    pll query(int jobl, int jobr, int l, int r, int i){
        if(jobl <= l && r <= jobr){
            return {g[i],f[i]};
        }
        int mid = (l + r) >> 1;
        down(i, mid - l + 1, r - mid);
        int x_g,x_f;
        bool fl=false,fr=false;
        pll tl,tr;
        if(jobl <= mid){
            fl=true;
            tl = query(jobl, jobr, l, mid, i << 1);
            
        }
        if(jobr > mid){
            fr=true;
            tr = query(jobl, jobr, mid + 1, r, i << 1 | 1);
        }

        if(fl&&fr){
            x_g = tl.first & tr.first;
            x_f = (tl.first & tr.second) | (tr.first & tl.second);
        }
        if(fl&&!fr){
            x_g = tl.first;
            x_f = tl.second;
        }
        if(!fl && fr){
            x_g = tr.first;
            x_f = tr.second;
        }

        return {x_g,x_f};
    }

    int find(int l, int r, int i, int x, int k){
        if(g[i] >> k & 1) return 0;
        if(l == r) return l;
        int mid= l + r >> 1;
        down(i, mid - l + 1, r - mid);
        if(x <= l){
            if(g[i << 1] >> k & 1) return find(mid + 1, r, i << 1 | 1, x , k);
            else return find( l, mid, i << 1, x, k);
        }else if(mid < x) return find(mid + 1, r, i<< 1 | 1, x, k);
        else{
            int t = find(l, mid, i << 1, x, k);
            if(!t) t = find(mid + 1, r, i << 1 | 1, x, k);
            return t;
        }
    }

};


void solve(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    SegmentTree st(n+10);
    st.build(1,n,1);
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,x;
            cin>>l>>r>>x;
            st.add(l,r,x,1,n,1);
        }else if(op==2){
            int s,x;
            cin>>s>>x;
            st.updata(s,x,1,n,1);
        }else{
            int l,r;
            cin>>l>>r;
            if(l==r){
                cout<<0<<"\n";
                continue;
            }

            pll t=st.query(l,r,1,n,1);
            
            if(t.second==0){
                cout<<t.first<<"\n";continue;
            }
            for(int i=63;i>=0;i--){
                if(t.second >> i & 1){
                    int p=st.find(1,n,1,l,i);
                    int ans=mask;
                    if(l<=p-1) ans &= st.query(l,p-1,1,n,1).first;
                    if(p+1<=r) ans &= st.query(p+1,r,1,n,1).first;
                    cout<<ans<<"\n";
                    break;
                }
            }
        }
    }
}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    // cin>>_;
    while(_--) solve();
    return 0;
}