[BZOJ4889][洛谷P3759][TJOI2017]不勤劳的图书管理员分块+树状数组

题目描述

加里敦大学有个帝国图书馆，小豆是图书馆阅览室的一个书籍管理员。他的任务是把书排成有序的，所以无序的书让他产生厌烦，两本乱序的书会让小豆产生这两本书页数的和的厌烦度。现在有n本被打乱顺序的书，在接下来m天中每天都会因为读者的阅览导致书籍顺序改变位置。因为小豆被要求在接下来的m天中至少要整理一次图书。小豆想知道，如果他前i天不去整理，第i天他的厌烦度是多少，这样他好选择厌烦度最小的那天去整理。

题解：

这题是我在中考完之后做的……当时在洛谷上只得了20分，其它全TLE，然后我就怀疑是常数太大了，毕竟有好多次树状数组的操作，当时就放弃了。今天又想填填坑，然后上网一搜题解，发现CQzhangyu的方法和我是一样的，只不过它的块的大小是

代码：（奇丑，慎抄）

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define Work \
if(a[x]<a[i])ans+=(v[x]+v[i]),Mod(ans);\
if(a[x]>a[i])ans-=(v[x]+v[i]),Mod(ans);\
if(a[y]<a[i])ans-=(v[y]+v[i]),Mod(ans);\
if(a[y]>a[i])ans+=(v[y]+v[i]),Mod(ans);
#define LL long long
const int maxn=;
const LL mod=+;
int read()
{
    int x=,f=;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<)+(x<<)+ch-'0';ch=getchar();}
    return x*f;
}
void Mod(LL &x){x=(x+mod)%mod;}
LL s[][maxn],s1[][maxn];
int n,m,a[maxn],belong[maxn],l[maxn],r[maxn];
LL v[maxn],block_v[];
void add(int x,LL y,int block){for(int i=x;i<=n;i+=(i&-i))s[block][i]=(s[block][i]+y)%mod;}
LL getsum(int x,int block){int r=;for(int i=x;i;i-=(i&-i))r=(r+s[block][i])%mod;return r;}
void add1(int x,int y,int block){for(int i=x;i<=n;i+=(i&-i))s1[block][i]+=y;}
int getsum1(int x,int block){int r=;for(int i=x;i;i-=(i&-i))r+=s1[block][i];return r;}
int main()
{
    n=read();m=read();
    for(int i=;i<=n;i++)a[i]=read(),v[i]=(LL)read();
    int o=(int)sqrt(n*);
    for(int i=;i<=n;i++)belong[i]=(i-)/o+,block_v[belong[i]]+=v[i];
    for(int i=;i<=n;i++)
    {
        if(!l[belong[i]])l[belong[i]]=i;
        r[belong[i]]=i;
    }
    LL ans=,tt=;
    for(int i=;i<=n;i++)
    {
        add(a[i],v[i],belong[i]);
        add1(a[i],,belong[i]);
        add(a[i],v[i],);
        add1(a[i],,);
        tt+=v[i];
        LL xx=(LL)getsum1(a[i],),yy=(LL)getsum(a[i],);
        ans+=(LL)(i-xx)*v[i]+tt-yy;
        Mod(ans);
    }
    while(m--)
    {
        int x=read(),y=read();
        if(x>y)swap(x,y);
        int bx=belong[x],by=belong[y];
        if(bx==by)for(int i=x+;i<y;i++){Work}
        else
        {
            for(int i=x+;i<=r[bx];i++){Work}
            for(int i=l[by];i<y;i++){Work}
            for(int i=bx+;i<by;i++)
            {
                ans+=(LL)(block_v[i]-getsum(a[x],i))+v[x]*(LL)(r[i]-l[i]+-getsum1(a[x],i)),Mod(ans);
                ans-=(LL)getsum(a[x]-,i)+v[x]*(LL)getsum1(a[x]-,i),Mod(ans);
                ans-=(LL)(block_v[i]-getsum(a[y],i))+v[y]*(LL)(r[i]-l[i]+-getsum1(a[y],i)),Mod(ans);
                ans+=(LL)getsum(a[y]-,i)+v[y]*(LL)getsum1(a[y]-,i),Mod(ans);
            }
        }
        if(a[x]<a[y])ans+=(v[x]+v[y]),Mod(ans);
        if(a[y]<a[x])ans-=(v[x]+v[y]),Mod(ans);
        printf("%lld\n",ans);
        add(a[x],-v[x],bx);add(a[y],-v[y],by);
        add(a[y],v[y],bx);add(a[x],v[x],by);
        add1(a[x],-,bx);add1(a[y],-,by);
        add1(a[y],,bx);add1(a[x],,by);
        block_v[bx]=block_v[bx]-v[x]+v[y];
        block_v[by]=block_v[by]-v[y]+v[x];
        swap(a[x],a[y]);swap(v[x],v[y]);
    }
}

[BZOJ4889][洛谷P3759][TJOI2017]不勤劳的图书管理员 分块+树状数组

题解：

代码：（奇丑，慎抄）

[BZOJ4889][洛谷P3759][TJOI2017]不勤劳的图书管理员分块+树状数组