dream

题意

给定一个长度在 10^9 内的序列，要求维护 3 种操作：

• 区间加
• 区间翻转
• 区间求和

强制在线。

思路

这三个操作明显对应平衡树（Splay/Treap）。考虑到序列的长度，需要动态开点。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=800000;
struct Splay
{
    struct Node
    {
        int c[2], fa;
        int len, siz;
        ll val, sum, add;
        bool rev;
    } tr[MAXN];
    int cnt, root;
    #define lc tr[x].c[0]
    #define rc tr[x].c[1]
    #define par tr[x].fa
    inline int newNode(int l, ll k)
    {
        int x=++cnt;
        lc=rc=par=0; tr[x].siz=tr[x].len=l;
        tr[x].val=k; tr[x].sum=l*k; tr[x].add=0; tr[x].rev=0;
        return x;
    }
    inline void pushup(int x)
    {
        tr[x].siz=tr[x].len; tr[x].sum=tr[x].len*tr[x].val;
        if (lc) tr[x].siz+=tr[lc].siz, tr[x].sum+=tr[lc].sum;
        if (rc) tr[x].siz+=tr[rc].siz, tr[x].sum+=tr[rc].sum;
    }
    inline void add(int x, ll k)
    {
        tr[x].val+=k; tr[x].sum+=tr[x].siz*k; tr[x].add+=k;
    }
    inline void rev(int x)
    {
        swap(lc, rc); tr[x].rev^=1;
    }
    inline void pushdown(int x)
    {
        if (tr[x].add)
        {
            if (lc) add(lc, tr[x].add);
            if (rc) add(rc, tr[x].add);
            tr[x].add=0;
        }
        if (tr[x].rev)
        {
            if (lc) rev(lc);
            if (rc) rev(rc);
            tr[x].rev=0;
        }
    }
    void pushall(int x)
    {
        if (par) pushall(par);
        pushdown(x);
    }
    inline bool getlr(int x)
    {
        return tr[par].c[1]==x;
    }
    inline void rotate(int x)
    {
        int y=par, z=tr[y].fa;
        bool k=getlr(x); int w=tr[x].c[k^1];
        if (z) tr[z].c[getlr(y)]=x; par=z;
        tr[y].c[k]=w; if (w) tr[w].fa=y;
        tr[x].c[k^1]=y; tr[y].fa=x; pushup(y);
    }
    void splay(int x, int y)
    {
        pushall(x);
        while (par!=y)
        {
            if (tr[par].fa!=y)
                rotate(getlr(x)^getlr(par)?x:par);
            rotate(x);
        }
        pushup(x);
        if (!y) root=x;
    }
    int find(int& p)
    {
        int x=root;
        while (x)
        {
            pushdown(x);
            if (lc&&p<=tr[lc].siz) x=lc;
            else if (rc&&p>tr[x].siz-tr[rc].siz)
                p-=tr[x].siz-tr[rc].siz, x=rc;
            else break;
        }
        p-=tr[lc].siz;
        return x;
    }
    void build(int n)
    {
        cnt=0; int x=newNode(n, 0);
        root=x;
        lc=newNode(0, 0); tr[lc].fa=x;
        rc=newNode(0, 0); tr[rc].fa=x;
        pushup(x);
    }
    int split(int x, int p)
    {
        splay(x, 0);
        int y=newNode(tr[x].len-p, tr[x].val); tr[x].len=p;
        tr[y].c[1]=rc; tr[rc].fa=y;
        rc=y; tr[y].fa=x;
        pushup(y); pushup(x);
        return y;
    }
    void update(int l, int r, int k)
    {
        int t1=l-1, t2=r;
        int x=find(t1); split(x, t1);
        int y=find(t2); y=split(y, t2);
        splay(x, 0); splay(y, x);
        add(tr[y].c[0], k);
        pushup(y); pushup(x);
    }
    void reverse(int l, int r)
    {
        int t1=l-1, t2=r;
        int x=find(t1); split(x, t1);
        int y=find(t2); y=split(y, t2);
        splay(x, 0); splay(y, x);
        rev(tr[y].c[0]);
        pushup(y); pushup(x);
    }
    ll query(int l, int r)
    {
        int t1=l-1, t2=r;
        int x=find(t1); split(x, t1);
        int y=find(t2); y=split(y, t2);
        splay(x, 0); splay(y, x);
        return tr[tr[y].c[0]].sum;
    }
    #undef lc
    #undef rc
    #undef par
} splay;
int main()
{
//  freopen("dream.in", "r", stdin);
//  freopen("dream.out", "w", stdout);
    int n, m, typ;
    scanf("%d%d%d", &n, &m, &typ);
    ll lans=0;
    splay.build(n);
    while (m--)
    {
        int opt; ll l, r, k;
        scanf("%d", &opt);
        switch (opt)
        {
            case 0:
                scanf("%lld%lld%lld", &l, &r, &k);
                if (typ) l^=lans, r^=lans, k^=lans;
                splay.update(l, r, k);
                break;
            case 1:
                scanf("%lld%lld", &l, &r);
                if (typ) l^=lans, r^=lans;
                splay.reverse(l, r);
                break;
            case 2:
                scanf("%lld%lld", &l, &r);
                if (typ) l^=lans, r^=lans;
                printf("%lld\n", lans=splay.query(l, r));
                break;
        }
    }
    return 0;
}

mage

题意

给定一个 n(n\leq 1000) 个点，m(m\leq \frac{n(n-1)}{2}) 的无向图，每个节点上有权。可以构造一个序列 h ，使这个图满足节点 i,j 间有边当且仅当 i<j 并且 h_i>h_j 。在这张图选取一个点集 S ，若 S 内的点两两没有连边且 S 外每一点都有连向 S 内点的边，则集合 S 对答案有 S 内点权和 乘 S 外点权和 的贡献。求所有点集的贡献和。

思路

观察这个图的特殊性质，发现对于任意三个节点 u,v,w ，它们的编号 u<v<w ，若 (u,v)\in E 且 (v,w)\in E ，则 (u,w)\in E 。这个性质告诉我们，在图中找一条链，则这条链上节点的诱导子图是一个团。考虑原图的补图，显然也有以上性质。再考虑第二条限制，若一点与当前集合中的点没有边（即再补图中都有边），则这个点也应该在当前集合中。所以会产生贡献的点集就是补图中的所有极大链。考虑 DP ，维护以每个点结尾的极大链数量 f1 /点权和 f2 /点权的平方和 f3 。如果一个点 i 与它后面的点没有连边，则它是一个极大链的结尾。记所有点的点权和为 Sum ，则它的贡献即为 Sum\cdot f2_i-f3_i 。

代码

#include <cstdio>
#include <bitset>
using namespace std;
const int MAXN=1100;
const int MOD=998244353;
int a[MAXN];
bitset<MAXN> b[MAXN];
bool g[MAXN][MAXN];
int f1[MAXN], f2[MAXN], f3[MAXN];
int main()
{
//  freopen("mage.in", "r", stdin);
//  freopen("mage.out", "w", stdout);
    int n, m, sum=0;
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    for (int i=1; i<=n; i++) sum+=a[i];
    for (int i=1; i<=m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u][v]=g[v][u]=1;
    }
    int ans=0;
    for (int i=1; i<=n; i++)
    {
        bool flag=0; b[i][i]=1;
        for (int j=i-1; j>=1; j--)
            if (!g[i][j]&&!b[i][j])
            {
                flag=1; b[i]|=b[j];
                f1[i]=(f1[i]+f1[j])%MOD;
                f2[i]=(f2[i]+f2[j]+1ll*f1[j]*a[i])%MOD;
                f3[i]=(f3[i]+f3[j]+2ll*f2[j]*a[i]+1ll*f1[j]*a[i]*a[i])%MOD;
            }
        if (!flag) f1[i]=1, f2[i]=a[i], f3[i]=a[i]*a[i];
        flag=0;
        for (int j=i+1; j<=n; j++)
            if (!g[i][j]) { flag=1; break; }
        if (!flag) ans=(ans+1ll*sum*f2[i]%MOD-f3[i]+MOD)%MOD;
    }
    printf("%d\n", ans);
    return 0;
}