TOJ 219 / 円円想要快點去玩！！

想法：

總之就是無修改強制在線逆序數對。
天啊，這題要預處理的東西多到炸。Orz

假設詢問的 l 戳在 第lid塊，r 戳在 第rid塊。

先把[lid, rid]中全部的逆序數對算出來：

考慮把它分塊處理，每一塊先維護自己的逆序對數。(myinv)
然後對每一塊預處理他到他後面每一塊，所產生的逆序對數。(inv_to)
然後把它弄成前綴和，可以O(1)知道某塊到後面某一塊中所有的逆序對數。(inv_to_sum)

然後再把多算的扣掉：

一開始會算出123456全部的逆序對數。
因為只想要4，所以要想辦法快速的把12356扣掉。

一開始預處理每一個數字對她右邊某一塊產生的逆序對數，和對自己那一塊的。(inv_single_to_rgt)
然後把它弄成前綴和，可以O(1)扣掉123。
往左的就反過來做，(inv_single_to_lft)
也可以O(1)扣掉356。

但是3多扣一次，所以要想辦法把它加回去。
在前面把每一塊的逆序對數算出來的時候，有順便把每一塊都sort好。
所以可以多記一個pos，表示這個數在塊中原本的位置，(sorted)
然後O(K)篩出紅色跟藍色部分，再O(K)把3算出來，加回去。

Code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#define maxn 30005
#define K 100
#define pii pair<int,int>
#define val first
#define pos second
using namespace std;
int n,q;
pii ar[maxn];
int len[maxn/K+5];
pii sorted[maxn/K+5][K+5];
int myinv[maxn/K+5];
int inv_to[maxn/K+5][maxn/K+5];
int inv_to_sum[maxn/K+5][maxn/K+5];
int inv_single_to_rgt[maxn/K+5][K+5][maxn/K+5];
int inv_single_to_lft[maxn/K+5][K+5][maxn/K+5];
pii ms[2][maxn];
int merge_sort(int l,int r,int p)
{
    if(l>=r)
        return 0;
    int mid=(l+r)/2;
    int ans=merge_sort(l,mid,p^1)+merge_sort(mid+1,r,p^1);
    int lpt=l,rpt=mid+1,pt=l;
    pii *prv=ms[p^1],*cur=ms[p];
    while(lpt<=mid&&rpt<=r)
    {
        if(prv[lpt].val<=prv[rpt].val)
            cur[pt++]=prv[lpt++];
        else
        {
            cur[pt++]=prv[rpt++];
            ans+=mid-lpt+1;
        }
    }
    while(lpt<=mid)
        cur[pt++]=prv[lpt++];
    while(rpt<=r)
        cur[pt++]=prv[rpt++];
    return ans;
}
void build_inv_per_block()
{
    memcpy(ms[0],ar,sizeof(pii)*n);
    memcpy(ms[1],ar,sizeof(pii)*n);
    for(int i=0;i*K<n;i++)
    {
        myinv[i]=merge_sort(i*K,i*K+len[i]-1,0);
        memcpy(sorted[i],ms[0]+i*K,sizeof(pii)*len[i]);
    }
}
void build_inv_nxt_block()
{
    for(int i=0;i*K<n;i++)
        for(int j=i+1;j*K<n;j++)
        {
            pii *lft=sorted[i],*rgt=sorted[j];
            int lpt=0,rpt=0;
            while(lpt<len[i]&&rpt<len[j])
            {
                if(lft[lpt].val>rgt[rpt].val)
                    inv_to[i][j]+=len[i]-lpt,rpt++;
                else
                    lpt++;
            }
        }
}
void build_inv_nxt_block_sum()
{
    for(int i=0;i*K<n;i++)
        for(int j=i+1;j*K<n;j++)
            inv_to_sum[i][j]=\
                inv_to_sum[i][j-1]+inv_to[i][j];
}
void build_inv_per_single_to_rgt()
{
    for(int i=0;i*K<n;i++)
    {
        int pt[maxn/K+5];
        memset(pt,0,sizeof(pt));
        for(int id=0;id<len[i];id++)
        {
            int p=sorted[i][id].pos-i*K;
            int x=sorted[i][id].val;
            int *ans=inv_single_to_rgt[i][p];
            
            for(int j=p+1;j<len[i];j++)//build self blk.
                if(x>ar[i*K+j].val)
                    ans[i]++;

            for(int j=i+1;j*K<n;j++)//build crs blk.
            {
                while(pt[j]<len[j] && sorted[j][pt[j]].val<x)
                    pt[j]++;
                ans[j]=pt[j];
            }
        }
    }
}
void build_inv_per_single_to_lft()
{
    for(int i=0;i*K<n;i++)
    {
        int pt[maxn/K+5];
        memset(pt,0,sizeof(pt));
        for(int id=len[i]-1;id>=0;id--)
        {
            int p=sorted[i][id].pos-i*K;
            int x=sorted[i][id].val;
            int *ans=inv_single_to_lft[i][p];

            for(int j=p-1;j>=0;j--)
                if(ar[i*K+j].val>x)
                    ans[i]++;

            for(int j=i-1;j>=0;j--)
            {
                while(pt[j]<len[j] && \
                        sorted[j][len[j]-1-pt[j]].val>x)
                    pt[j]++;
                ans[j]=pt[j];
            }
        }
    }
}
void build_inv_per_single_to_rgt_sum()
{
    for(int i=0;i*K<n;i++)
        for(int p=0;p<len[i];p++)
            for(int j=i;j*K<n;j++)
                inv_single_to_rgt[i][p][j]=\
                inv_single_to_rgt[i][p][j-1]+\
                inv_single_to_rgt[i][p][j];
}
void build_inv_per_single_to_lft_sum()
{
    for(int i=0;i*K<n;i++)
        for(int p=0;p<len[i];p++)
            for(int j=i;j>=0;j--)
                inv_single_to_lft[i][p][j]=\
                inv_single_to_lft[i][p][j+1]+\
                inv_single_to_lft[i][p][j];
}
void build()
{
    for(int i=0;i*K<n;i++)
        len[i]=min(K,n-i*K);
    build_inv_per_block();
    build_inv_nxt_block();
    build_inv_nxt_block_sum();
    build_inv_per_single_to_rgt();
    build_inv_per_single_to_lft();
    build_inv_per_single_to_rgt_sum();
    build_inv_per_single_to_lft_sum();
}
int ask(int l,int r)
{
    int lid=l/K;
    int rid=r/K;
    int ans=0;
    for(int i=lid;i<=rid;i++)
        ans+=myinv[i];
    for(int i=lid;i<=rid;i++)
        ans+=inv_to_sum[i][rid];
    for(int i=0;i<l-lid*K;i++)
        ans-=inv_single_to_rgt[lid][i][rid];
    for(int i=len[rid]-1;i>r-rid*K;i--)
        ans-=inv_single_to_lft[rid][i][lid];

    int lpt=0,rpt=0;
    pii *lft=sorted[lid],*rgt=sorted[rid];
    vector<pii> lc,rc;
    while(lpt<len[lid])
    {
        while(lpt<len[lid] && lft[lpt].pos>=l)
            lpt++;
        if(lpt==len[lid])
            break;
        lc.push_back(lft[lpt++]);
    }
    while(rpt<len[rid])
    {
        while(rpt<len[rid] && rgt[rpt].pos<=r)
            rpt++;
        if(rpt==len[rid])
            break;
        rc.push_back(rgt[rpt++]);
    }
    lpt=rpt=0;
    while(lpt<(int)lc.size()&&rpt<(int)rc.size())
    {
        if(lc[lpt].val>rc[rpt].val)
            ans+=(int)lc.size()-lpt,rpt++;
        else
            lpt++;
    }
    return ans;
}
void sol()
{
    int l,r;
    scanf("%d%d",&l,&r);
    for(int i=1;i<=q;i++)
    {
        int ans=ask(l-1,r-1);
        printf("%d\n",ans);
        l=min((0LL+ans+2217+i+1)%n,(1LL*ans*2217+i+1)%n)+1;
        r=max((0LL+ans+2217+i+1)%n,(1LL*ans*2217+i+1)%n)+1;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&ar[i].val);
        ar[i].pos=i;
    }
    scanf("%d",&q);
    build();
    sol();
    return 0;
}