太菜了只能参加TG组

隔壁PJ考的比TG难是怎么肥事？？

爆蛋过程

8：20起床

然后一边等题目加载一边吔早饭，ccf这什么破服务器

8：40才看到题面，先把ABC都看了一遍

先把A50分打了，然后去想B （9：00）

B推了半天推出了交换相邻最多只会影响逆序对数1个的结论，但还是没想出40分做法，又回去看A

然后发现A的60分判个奇偶性就行了（不知道对不对），然后一会就打完了，（9：30

然后又去推B，瞎推竟然推出来一个结论：（9：50

定义 \(s_i\) 为第 \(i\) 个数前比第 \(i\) 个数大的数，那么每一次操作都会把所有 \(s_i\) 往前移动1位并且都减去1，0不用减

那么就是要查询一段区间内大于某个数的数字的和以及个数

我当时想这是个动态二维数点问题，然后不断尝试写二维BIT啥的

在10：50的时候我突然想到，\(s_1\) 一定是0，那么就变成了查询整个数组内大于某个数的数字和以及个数

权！值！线！段！树！

11：00过了样例，11：10完成对拍

然后C题对于每个k就相当于n个数组成几个大小相同的环，枚举因数即可，暴力模拟答案

在11：59：43调完交了上去

不过有个地方写炸了，所以可能爆蛋/kk

期望得分：60+100+100=260

听说C班除了我都AK了QAQ/kk %%%%%%%%%%%%%%%%%%%%%%%%

题解

A

对于 1~5，直接判断 \(a_1-b_1\) 是否等于 \(a_2-b_2\) 即可

对于 6~10，判断 \(a_1-b_1=b_2-a_2\) 或者 \(a_2-b_2=b_1-a_1\) ，两个满足一个即可

对于 11~12，如果 \(t=1\) 和 \(t=2\) 的操作只有其中一个那么直接按照 1~10 里的做法做

否则判断一下奇偶性即可，判断 \((a_1-b_1) \bmod 2 = (a_2-b_2) \bmod 2\) 即可

剩下不会了，预计得分 60

// This code wrote by chtholly_micromaker(MicroMaker)
#include <bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
const int MaxN=100050;
struct Quetion
{
    int t,u,v;
}Q[MaxN];
template <class t> inline void read(t &s)
{
    s=0;
    reg int f=1;
    reg char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c))
        s=(s<<3)+(s<<1)+(c^48),c=getchar();
    s*=f;
    return;
}
int n,m;
int a[MaxN],b[MaxN];
namespace SUBTASK1
{
    inline void solve()
    {
        if(a[1]-b[1]==a[2]-b[2])
            puts("YES");
        else
            puts("NO");
        return;
    }
}
namespace SUBTASK2
{
    inline void solve()
    {
        if((a[1]-b[1]==b[2]-a[2])||(a[2]-b[2]==b[1]-a[1]))
            puts("YES");
        else
            puts("NO");
        return;
    }
}
namespace SUBTASK3
{
    inline void solve(int c1,int c2)
    {
        if(c1&&c2)
        {
            if(((a[1]-b[1])&1)==((a[2]-b[2])&1))
                puts("YES");
            else
                puts("NO");
            return;
        }
        else
        {
            if(c1)
                SUBTASK1::solve();
            else
                SUBTASK2::solve();
        }
        return;
    }
}
inline void work()
{
    read(n);read(m);
    for(int i=1;i<=n;++i)
        read(a[i]);
    for(int i=1;i<=n;++i)
        read(b[i]);
    reg int cnt1=0,cnt2=0;
    for(int i=1;i<=m;++i)
    {
        read(Q[i].t);read(Q[i].u);read(Q[i].v);
        if(Q[i].t==2)
            ++cnt2;
        if(Q[i].t==1)
            ++cnt1;
    }
    if(n==2&&m==1&&cnt1)
    {
        SUBTASK1::solve();
        return;
    }
    if(n==2&&m==1&&cnt2)
    {
        SUBTASK2::solve();
        return;
    }
    if(n==2)
    {
        SUBTASK3::solve(cnt1,cnt2);
        return;
    }
    return;
}
signed main(void)
{

    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);

    int t;cin>>t;
    while(t--)
        work();
    return 0;
}

B

我们设原序列为 \(a_i\)，\(s_i\) 为 \(a_1,a_2,\cdots,a_{i-1}\) 中大于 \(a_i\) 的数的个数

对于一个 \(a\) 序列求 \(s\) 序列可以用树状数组 \(O(n\log n)\) 实现

我们来看一个例子（假设 \(s_i\) 已经求好了）

a: 1 4 3 5 2
s: 0 0 1 0 3

一轮冒泡后

a: 1 3 4 2 5
s: 0 0 0 2 0

一会发现每个大于 0 的 \(s_i\) 都减去了 1 并且所有 \(s_i\) 都往左移了一位

然后你会发现，\(s_1\) 一定为 0 （由 \(s_i\) 的定义可知）

那么左移操作就可以忽略，那么 \(t=2\) 的操作就变成了

求当前 \(a\) 序列的 \(\sum_{i=1}^n \max(s_i-c,0)\)

那么也就是询问（这里序列指 \(s\) 序列）
\[ \text{序列内所有大于} c \text{的数字的和}-\text{序列内大于} c \text{的数字的个数}\times c \]
这个直接权值线段树维护就行（或者两个树状数组也可以）

现在，如果交换操作直接暴力重新求 \(s\) 序列就能拿到 60 分了

但离 100 分已经不远了

我们还是来观察一下：

假设 \(p<q\)

a: p q
s: x y

交换 \(p,q\) ，因为 \(p<q\) 所以 \(p\) 对应的 \(s\) 要 \(+1\) ，而 \(q\) 对应的 \(s\) 不会变

a: q p
s: y x+1

\(p>q\) 也差不多

所以利用这个性质我们每次交换操作只要单点修改一下 \(s\) 就行，单次修改复杂度 \(O(\log n)\)

总时间复杂度 \(O(m\log n)\)

// This code wrote by chtholly_micromaker(MicroMaker)
#include <bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
const int MaxN=200050;
template <class t> inline void read(t &s)
{
    s=0;
    reg int f=1;
    reg char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c))
        s=(s<<3)+(s<<1)+(c^48),c=getchar();
    s*=f;
    return;
}
int n,m;
int a[MaxN],b[MaxN];
int tr[MaxN];
int val[MaxN<<2];
int sum[MaxN<<2];
inline int lowbit(int x)
{
    return x&(-x);
}
inline void modify(int x,int k)
{
    while(x<=n)
    {
        tr[x]+=k;
        x+=lowbit(x);
    }
    return;
}
inline int queryP(int x)
{
    reg int res=0;
    while(x>0)
    {
        res+=tr[x];
        x-=lowbit(x);
    }
    return res;
}
inline int query(int l,int r)
{
    return queryP(r)-queryP(l-1);
}
#define lson (u<<1)
#define rson (u<<1|1)
inline void Spushup(int u)
{
    val[u]=val[lson]+val[rson];
    sum[u]=sum[lson]+sum[rson];
    return;
}
inline void Smodify(int u,int l,int r,int p,int k)
{
    if(l==r)
    {
        // printf("Smodify %lld %lldx%lld\n",u,k,l);
        val[u]+=k;
        sum[u]+=k*l;
        return;
    }
    reg int mid=(l+r)>>1;
    if(p<=mid)
        Smodify(lson,l,mid,p,k);
    else
        Smodify(rson,mid+1,r,p,k);
    Spushup(u);
    return;
}
inline pair<int,int> Squery(int u,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)
        return make_pair(val[u],sum[u]);
    reg int mid=(l+r)>>1;
    reg pair<int,int> res=make_pair(0,0);
    if(ql<=mid)
    {
        reg pair<int,int> t=Squery(lson,l,mid,ql,qr);
        res.first+=t.first;
        res.second+=t.second;
    }
    if(mid<qr)
    {
        reg pair<int,int> t=Squery(rson,mid+1,r,ql,qr);
        res.first+=t.first;
        res.second+=t.second;
    }
    // printf("Squery %lld %lld is %lld %lld\n",l,r,res.first,res.second);
    return res;
}
inline void recalc()
{
    // memset(tr,0,sizeof tr);
    // memset(val,0,sizeof val);
    // memset(sum,0,sizeof sum);
    for(int i=1;i<=n;++i)
    {
        b[i]=query(a[i],n);
        // printf("recalc %lld is %lld\n",i,t);
        if(b[i])
            Smodify(1,1,n,b[i],1);
        modify(a[i],1);
    }
    return;
}
inline void work(int i,int j)
{
    if(a[i]>a[j])
    {
        if(b[j]>0)
            Smodify(1,1,n,b[j],-1);
        --b[j];
        if(b[j]>0)
            Smodify(1,1,n,b[j],1);
        swap(a[i],a[j]);
        swap(b[i],b[j]);
    }
    else
    {
        if(b[i]>0)
            Smodify(1,1,n,b[i],-1);
        ++b[i];
        if(b[i]>0)
            Smodify(1,1,n,b[i],1);
        swap(a[i],a[j]);
        swap(b[i],b[j]);
    }
    return;
}
signed main(void)
{

    freopen("bubble.in","r",stdin);
    freopen("bubble.out","w",stdout);

    cin>>n>>m;
    for(int i=1;i<=n;++i)
        read(a[i]);
    recalc();
    reg int t,c;
    for(int i=1;i<=m;++i)
    {
        read(t);read(c);
        if(t==1)
        {
            // swap(a[c],a[c+1]);
            work(c,c+1);
        }
        else
        {
            if(c>=n)
                puts("0");
            else
            {
                reg pair<int,int> res=Squery(1,1,n,c+1,n);
                // printf("query %lld %lld is %lld %lld\n",c+1,n,res.first,res.second);
                printf("%lld\n",res.second-res.first*c);
            }
        }
    }
    return 0;
}

C

先大力手玩一下，发现环的长度为 \(\frac n {\gcd(n,k)}\)

环长度相同答案一定相同，所以直接枚举因子，预处理

\(\{ 1,2,3,4,5,6 \}\) 在 \(k=1\) 的时候放成 \(\{ 2,4,6,5,3,1 \}\)

可以发现，从大到小来说的话，先放 6 ，6 的右边放 5 ，6 的左边放 4，6的右边的右边放 3，6 的左边的左边放 2

于是很显然，弄两个指针就行

然后 \(k>1\) 的时候就对每个环进行这样的处理即可

记得特别处理一下 \(k=0\) 的情况

// This code wrote by chtholly_micromaker(MicroMaker)
#include <bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
const int MaxN=200050;
template <class t> inline void read(t &s)
{
    s=0;
    reg int f=1;
    reg char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c))
        s=(s<<3)+(s<<1)+(c^48),c=getchar();
    s*=f;
    return;
}
int n;
int a[MaxN],b[MaxN],ans[MaxN];
int thezero;
inline int dfs(int l,int r)
{
    // printf("dfs %lld %lld\n",l,r);
    reg int L=1e5;
    reg int R=1e5-1;
    for(int i=r;i>=l;--i)
        if(i&1)
            b[++R]=a[i];
        else
            b[--L]=a[i];
    reg int res=0;
    for(int i=L;i<=R;++i)
        if(i==R)
            res+=b[R]*b[L];
        else
            res+=b[i]*b[i+1];
    // puts("ok");
    return res;
}
inline int gcd(int a,int b)
{
    return !b?a:gcd(b,a%b);
}
signed main(void)
{

    // freopen("ring.in","r",stdin);
    // freopen("ring.out","w",stdout);

    int m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        read(a[i]),thezero+=a[i]*a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<n;++i)
        if(!(n%i))
        {
            for(int j=1;j<=n;j+=n/i)
                ans[i]+=dfs(j,j+n/i-1);
        }
    for(int i=1;i<=m;++i)
    {
        reg int c;
        read(c);
        if(!c)
            printf("%lld\n",thezero);
        else
            printf("%lld\n",ans[gcd(c,n)]);
    }
    return 0;
}