How to AK ABC265

__vector__ · 2022-08-21 22:01:09 · 个人记录

题外话

第一次打出 1200 以上的表现分，上绿了。

A&B&C

略过

D

枚举每一个位置作为 x，然后利用前缀和二分得出 y,z,w。

E

设状态 dp_{i,j,k} 表示第一种组合使用数量为 i，第二种组合使用数量为 j，第三种组合数量为 k 的方案数。

#include <bits/stdc++.h>
using namespace std;
namespace Main {
    typedef long long ll;
    const ll mod=998244353;
    const int maxn=305;
    map<pair<ll,ll>,bool> mp;
    ll f[maxn][maxn][maxn];
    int n,m;
    ll A,B,C,D,E,F;
    void main() {
        scanf("%d%d",&n,&m);
        scanf("%lld%lld%lld%lld%lld%lld",&A,&B,&C,&D,&E,&F);
        ll x,y;
        for(int i=1; i<=m; i++) {
            scanf("%lld%lld",&x,&y);
            mp[make_pair(x,y)]=1;
        }
        f[0][0][0]=1;
        for(ll i=0; i<=n; i++) {
            for(ll j=0; j<=n-i; j++) {
                for(ll k=0; k<=n-i-j; k++) {
                    if(mp[make_pair(i*A+j*C+k*E,i*B+j*D+k*F)]) {
                        continue;
                    }
                    if(i) {
                        f[i][j][k]+=f[i-1][j][k];
                    }
                    if(j) {
                        f[i][j][k]+=f[i][j-1][k];
                    }
                    if(k) {
                        f[i][j][k]+=f[i][j][k-1];
                    }
                    f[i][j][k]%=mod;
                }
            }
        }
        ll ans=0;
        for(ll i=0; i<=n; i++) {
            for(ll j=0; j<=n-i; j++) {
                ll k=n-i-j;
                ans+=f[i][j][k];
                ans%=mod;
            }
        }
        printf("%lld",ans);
    }
}
int main() {
    Main::main();
    return 0;
}  

F

在想

G

这道题由于我之前维护 6 个 tag 的做法假了，所以我只会邹神的做法。 我搞的分块做法 AC了。
感觉 6 个 tag 的做法应该还是能做的，但是修改很麻烦，我一个 pushdown 能写几十行。

区间逆序对的数量由 (1,0),(2,0),(2,1) 这样数对的数量决定。

维护序列，那就用线段树。

想一下如何合并左右子树信息（就是怎么让左右子树信息可以相加得到当前信息）。

显然是左右子树区间各自的逆序对数，以及左右子树区间之间形成的逆序对数相加。（也就说明了和左右子树区间原本的答案，以及左右区间各自的每个数出现的次数有关）

所以：

对于每一个节点，用 g_{i,j} 维护它对应的区间的逆序对数（相当于记录自己原本的答案，合并到父节点时要用到），具体是：有多少个数值 i 在数值 j 前面。

同时每个节点都还要维护一个 cnt 数组，代表它对应的区间每个值出现次数，方便合并信息。

左右子树合并信息时，用各自的 g 数组和 cnt 数组就能快速（常数时间）得到结果了。现在

那修改操作怎么办？

每个节点维护一个数组 turn 代表这个节点对应的区间每个数应该以什么形式转换。（相当于对于子树的 lazy_tag）

进行修改时，就在标记下方的时候，按照常规操作，把子树的 lazy_tag 加上当前的 lazy_tag，并将子树的信息按照本节点的 lazy_tag 进行转换。

查询的时候，就将查找区间内找到的几个节点记录下来，直接把对应区间记录的信息扒下来就行了，注意一个区间可以由好几个节点组成，要将这几个节点按照左右顺序合并再输出答案（合并方式就是之前所说的合并左右子树的方式，直接相加信息）

#include <bits/stdc++.h>
using namespace std;
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
namespace Main {
    typedef long long ll;
    const int maxn=1e5+5;
    int n;
    int a[maxn];
    int q;
    struct Replace {
        int turn[3];
        void init() {
            turn[0]=0;
            turn[1]=1;
            turn[2]=2;
        }
        Replace operator +(const Replace& b) {
            Replace res;
            for(int i=0; i<3; i++) {
                res.turn[i]=b.turn[turn[i]];
            }
            return res;
        }
    };
    struct Information {
        ll g[3][3];
        ll cnt[3];
        Information() {
            memset(g,0,sizeof g);
            memset(cnt,0,sizeof cnt);
        }
        Information operator +(const Information& b) {
            Information res;
            for(int i=0; i<3; i++)res.cnt[i]=cnt[i]+b.cnt[i];
            for(int i=0; i<3; i++) {
                for(int j=0; j<3; j++) {
                    res.g[i][j]=g[i][j]+b.g[i][j];
                    res.g[i][j]+=cnt[i]*b.cnt[j];
                }
            }
            return res;
        }
        ll sum()
        {
            ll res=0;
            for(int i=0;i<3;i++)
            {
                for(int j=0;j<i;j++)
                {
                    res+=g[i][j];
                }
            }
            return res;
        }
    };
    Information Modify(Information information,Replace replace) {
        Information res;
        for(int i=0; i<3; i++) {
            res.cnt[replace.turn[i]]+=information.cnt[i];
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                res.g[replace.turn[i]][replace.turn[j]]+=information.g[i][j];
            }
        }
        return res;
    }
    struct Tree {
        Information information;
        Replace replace_tag;
        int l,r;
    } tree[maxn<<2];
    void pushup(int i)
    {
        tree[i].information=tree[ls(i)].information+tree[rs(i)].information;
    }
    void pushdown(int i)
    {
        tree[ls(i)].replace_tag=tree[ls(i)].replace_tag+tree[i].replace_tag;
        tree[ls(i)].information=Modify(tree[ls(i)].information,tree[i].replace_tag);
        tree[rs(i)].replace_tag=tree[rs(i)].replace_tag+tree[i].replace_tag;
        tree[rs(i)].information=Modify(tree[rs(i)].information,tree[i].replace_tag);
        tree[i].replace_tag.init();
    }
    void build(int i,int l,int r)
    {
        tree[i].l=l;
        tree[i].r=r;
        tree[i].replace_tag.init();
        if(l==r)
        {
            tree[i].information.cnt[a[l]]=1;
            return;
        }
        int mid=l+r>>1;
        build(ls(i),l,mid);
        build(rs(i),mid+1,r);
        pushup(i);
    }

    void change(int i,int l,int r,Replace replace)
    {
        if(tree[i].l>=l&&tree[i].r<=r)
        {
            tree[i].replace_tag=tree[i].replace_tag+replace;
            tree[i].information=Modify(tree[i].information,replace);
            return;
        }
        if(tree[i].r<l||tree[i].l>r)return;
        pushdown(i);
        int mid=tree[i].l+tree[i].r>>1;
        if(mid>=l)change(ls(i),l,r,replace);
        if(mid<r)change(rs(i),l,r,replace);
        pushup(i);
    }
    Information query(int i,int l,int r)
    {
        if(tree[i].l>=l&&tree[i].r<=r)
        {
            return tree[i].information;
        }
        pushdown(i);
        int mid=tree[i].l+tree[i].r>>1;
        Information ans;
        if(mid>=l)ans=ans+query(ls(i),l,r);
        if(mid<r)ans=ans+query(rs(i),l,r);
        return ans;
    }
    void main() {
        scanf("%d%d",&n,&q);
        for(int i=1; i<=n; i++) {
            scanf("%d",&a[i]);
        }
        build(1,1,n);
        int op,l,r,s,t,u;
        while(q--) {
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d%d",&l,&r);
                printf("%lld\n",query(1,l,r).sum());
            }
            if(op==2)
            {
                scanf("%d%d%d%d%d",&l,&r,&s,&t,&u);
                Replace rep;
                rep.turn[0]=s;
                rep.turn[1]=t;
                rep.turn[2]=u;
                change(1,l,r,rep);
            }
        }
    }
}
int main() {
    Main::main();
    return 0;
}  

我再说一下这道题的分块做法。

我的做法是，整块打 lazytag 进行修改，散块暴力修改，同时维护区间答案。

查询时整块直接查询区间答案加上lazytag，散块暴力（也要加上所在块的 lazytag），同时将查询到的信息合并。

来说一下细节：

1. 对整块修改时，将区间的 lazytag 根据 S,T,U 进行转换。
2. 对散块修改时，暴力修改元素的时候，不仅还要算上本次修改的，还要算上本区间之前的 lazytag（如果这个区间还有 tag，那说明之前没修改完）。另外由于本次修改时已经算上了之前的 lazytag，还要将对应区间的 lazytag 去掉，防止当前修改的这些元素被重复修改。但是这个区间有的元素之前被打了修改标记，但是当前并没有完成修改，直接去掉区间 lazytag 会导致漏修改这些元素，所以还要把那些 lazytag 被去掉但是之前的修改没有被应用的元素，在 lazytag 去掉之前完成修改（显然这个修改就要根据本区间原来已有的tag，而不包括本次修改加上的 tag了）。

总结一句话，细节超多。

#include <bits/stdc++.h>
using namespace std;
namespace Main {
    typedef long long ll;
    const int maxn=1e5+5;
    int n;
    int a[maxn];
    int q;
    struct Replace {
        int turn[3];
        void init() {
            turn[0]=0;
            turn[1]=1;
            turn[2]=2;
        }
        Replace operator +(const Replace& b) {
            Replace res;
            for(int i=0; i<3; i++) {
                res.turn[i]=b.turn[turn[i]];
            }
            return res;
        }
    };
    struct Information {
        ll g[3][3];
        ll cnt[3];
        Information() {
            memset(g,0,sizeof g);
            memset(cnt,0,sizeof cnt);
        }
        Information operator +(const Information& b) {
            Information res;
            for(int i=0; i<3; i++)res.cnt[i]=cnt[i]+b.cnt[i];
            for(int i=0; i<3; i++) {
                for(int j=0; j<3; j++) {
                    res.g[i][j]=g[i][j]+b.g[i][j];
                    res.g[i][j]+=cnt[i]*b.cnt[j];
                }
            }
            return res;
        }
        ll sum()
        {
            ll res=0;
            for(int i=0;i<3;i++)
            {
                for(int j=0;j<i;j++)
                {
                    res+=g[i][j];
                }
            }
            return res;
        }
    };
    Information Modify(Information information,Replace replace) {
        Information res;
        for(int i=0; i<3; i++) {
            res.cnt[replace.turn[i]]+=information.cnt[i];
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                res.g[replace.turn[i]][replace.turn[j]]+=information.g[i][j];
            }
        }
        return res;
    }
    int blocks,len;
    int id[maxn];
    Information lazy[maxn];//记录块整体信息 
    Replace lazyrep[maxn];
    Information val[maxn];//单个元素信息 
    int L[maxn],R[maxn];//每个块的左右端点 
    ll query(int l,int r)
    {
        Information res;
        if(id[l]==id[r])
        {
            for(int i=l;i<=r;i++)
            {
                res=res+Modify(val[i],lazyrep[id[l]]);
            }
            return res.sum();
        }
        if(id[l]!=id[r])
        {
            for(int i=l;i<=R[id[l]];i++)
            {
                res=res+Modify(val[i],lazyrep[id[l]]);
            }
            for(int i=id[l]+1;i!=id[r];i++)
            {
                res=res+Modify(lazy[i],lazyrep[i]);
            }
            for(int i=L[id[r]];i<=r;i++)
            {
                res=res+Modify(val[i],lazyrep[id[r]]);
            }
            return res.sum();
        }
    }
    void change(int l,int r,Replace replace)
    {
        if(id[l]==id[r])
        {
            for(int i=l;i<=r;i++)
            {
                val[i]=Modify(val[i],lazyrep[id[l]]+replace);
            }
            Information tmp;
            for(int i=L[id[l]];i<=R[id[l]];i++)
            {
                if(i<l||i>r)
                    val[i]=Modify(val[i],lazyrep[id[l]]);
                tmp=tmp+val[i];
            }
            lazy[id[l]]=tmp;
            lazyrep[id[l]].init();
        }
        if(id[l]!=id[r])
        {
            for(int i=l;i<=R[id[l]];i++)
            {
                val[i]=Modify(val[i],lazyrep[id[l]]+replace);
            }
            Information tmp;
            for(int i=L[id[l]];i<=R[id[l]];i++)
            {
                if(i<l)
                    val[i]=Modify(val[i],lazyrep[id[l]]);
                tmp=tmp+val[i];
            }
            lazy[id[l]]=tmp;
            lazyrep[id[l]].init();
            for(int i=id[l]+1;i!=id[r];i++)
            {
                lazyrep[i]=lazyrep[i]+replace;
            }
            for(int i=L[id[r]];i<=r;i++)
            {
                val[i]=Modify(val[i],lazyrep[id[r]]+replace);
            }
            Information tmp2;
            for(int i=L[id[r]];i<=R[id[r]];i++)
            {
                if(i>r)
                    val[i]=Modify(val[i],lazyrep[id[r]]);
                tmp2=tmp2+val[i];
            }
            lazy[id[r]]=tmp2;
            lazyrep[id[r]].init();
        }
    }
    void main() {
        scanf("%d%d",&n,&q);
        len=sqrt(n);
        for(int i=1; i<=n; i++) {
            scanf("%d",&a[i]);
            val[i].cnt[a[i]]++;
            id[i]=(i-1)/len+1;
            lazy[id[i]]=lazy[id[i]]+val[i];
        }
//      printf("sum: %lld\n",lazy[1].sum());
        for(int i=1;i<=n;i++)
        {
            if(id[i]!=id[i-1])
            {
                L[id[i]]=i;
            }
            if(id[i]!=id[i+1])
            {
                R[id[i]]=i;
            }
            lazyrep[id[i]].init();
        }
        int op,l,r,s,t,u;
        while(q--) {
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d%d",&l,&r);
                printf("%lld\n",query(l,r));
            }
            if(op==2)
            {
                scanf("%d%d%d%d%d",&l,&r,&s,&t,&u);
                Replace rep;
                rep.turn[0]=s;
                rep.turn[1]=t;
                rep.turn[2]=u;
                change(l,r,rep);
            }
        }
    }
}
int main() {
    Main::main();
    return 0;
}  

Ex

在想