https://codeforc.es/contest/1443/problem/E

观察q是1e5,x是1e5,所以最多后移15位,所以我们暴力模拟这个进位过程以及修改前缀和即可,老实说代码挺难写的.代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
ll fac[20];
ll sum[N];
bool vis[N];
int main()
{
    int n,m;//个数 操作
    scanf("%d%d",&n,&m);
    for(ll i=1;i<=n;i++)   sum[i]+=sum[i-1]+i;
    fac[0]=1;
    for(ll i=1;i<=15;i++)  fac[i]=fac[i-1]*i;
    int st=max(1,n-14);
    ll cnt=1,now=1;//初始位子为1.
    for(int i=1;i<=m;i++)
    {
        int l,r,x,op;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d",&l,&r);
            printf("%lld\n",sum[r]-sum[l-1]);
        }
        else
        {
            scanf("%d",&x);cnt+=x;
            now=cnt;
            for(int i=st;i<=n;i++)  vis[i]=false;
            for(int i=st;i<=n;i++)
            {
                ll temp=0;
                for(int j=st;j<=n;j++)
                {
                    if(!vis[j])
                    {
                        temp+=fac[n-i];
                        if(temp>=now)
                        {
                            now-=(temp-fac[n-i]);
                            sum[i]=sum[i-1]+j;
                            vis[j]=true;
                            break;
                        }
                    }
                }
            }
        }
    }
    return 0;
}

https://codeforc.es/contest/1445/problem/E
题目是给你n个人.m组关系.以及k组,要你在k组中任选两组构成二分图.问你方案数?
一个dsu即可解决的图论问题,当你不懂这个的时候,确实会觉得挺难的,注释一下可撤销并查集只是为了初始化而已...思路是这样的:先处理组内不能构成二分图的,然后再处理每条边(都是可能不能组成二分图的),再拿答案-它即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+51;
int c[N];
bool ok[N];//判断这组是不是有用.
struct node{
    int n1;//a
    int n2;//b
    int c1;//min(c[a],c[b])
    int c2;//max(c[a],c[b])
    ll val;//存信息的.
}v[N];
int fa[N<<1],n;
stack<pair<int,int> >roll;//第一维存现在的信息,第二维存父亲信息.
bool cmp(node a,node b)
{
    return a.val<b.val;
}

ll find(int x)
{
    int r=x;ll cnt=0;//cnt记录路径奇偶性.
    while(fa[r]!=r)
    {
        r=fa[r],cnt++;
    }
    ll ans=cnt*N+r;
    if(cnt%2==0) x=fa[x],--cnt;
    while(cnt>16)
    {
        int i=fa[x];
        fa[x]=r;
        x=fa[i];
        cnt-=2;
    }//奇数直接连根.偶数缩点.
    return ans;
}

bool join(int a,int b)//假如有奇数环就无法加入.
{
    ll fx=find(a),fy=find(b);
    int ra=fx%N,rb=fy%N;
    int la=fx/N,lb=fy/N;
    if(ra==rb)
    {
        return (la+lb)%2==1;
    }
    else
    {
        roll.push(pair<int,int>(ra,fa[ra]));
        if((la+lb)%2)
        {
            fa[ra]=++n,fa[n]=rb;
        }
        else fa[ra]=rb;
        return true;
    }
}

void roll_back()
{
    while(roll.size())
    {
        pair<int,int>pr=roll.top();
        roll.pop();
        fa[pr.first]=pr.second;
    }
}

int main()
{
    int m,id=0;ll k;
    scanf("%d%d%lld",&n,&m,&k);
    for(int i=1;i<=N*2-4;i++)   fa[i]=i;
    for(int i=1;i<=n;i++)   scanf("%d",c+i);
    //for(int i=1;i<=m;i++)   scanf("%d%d",a+i,b+i);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(c[a]==c[b])//在同一组的.
        {
            if(!join(a,b)&&!ok[c[a]])
            {
                k--;
                ok[c[a]]=1;
            }
        }
        else//在不同组的.
        {
            v[id].n1=a;
            v[id].n2=b;
            v[id].c1=min(c[a],c[b]);
            v[id].c2=max(c[a],c[b]);
            v[id].val=1ll*v[id].c1*N+v[id].c2;
            id++;
        }
    }ll ans=k*(k-1)/2;
    while(!roll.empty())roll.pop();
    sort(v,v+id,cmp);
    bool flag=false;//false代表两个组可能组成二分图.
    for(int i=0;i<id;i++)
    {
        int a=v[i].n1;int b=v[i].n2;
        if(ok[c[a]]||ok[c[b]])  continue;
        if(i>0&&v[i].val!=v[i-1].val)
        {
            flag=0;
            roll_back();
        }
        if(!join(a,b))
        {
            if(!flag) ans--;
            flag=1;
        }
    }
    printf("%lld\n",ans);
    return 0;
}
/*
5 5 2
1 2 1 2 1
1 2
2 3
3 4
4 5
5 1


0
*/

300ms可过...