gayyyyyyyyyy

原题解：http://hzwer.com/8053.html
联动：https://pst.iorinn.moe/archives/TLEBA.html

T1

naive

T2

二分
这就引进了第二个数组和块内实施保持有序的操作
还得记得打标记

T3

一样
二分查找

T4

加上了区间修改
对完整的块和不完整的块分别统计就行

T5

从本题开始复杂度变成 $O(玄学 / 能过)$
本题操作骚
每个数最多被开方 4 次
如果某个块被开方成了全部都是 0 / 1 的玩意，就可以跳过它
然后暴力就行

T6

插入
教你怎么暴力重构
vector 大法吼啊

T7

加上了区间乘法
则加两个 lazy 标记
对不完整块进行改动时，需要 pushdown

等等，我串戏了，这好像不是线段树。

事实上跟线段树确实挺像。不如说，通过线段树是一个很好的思考怎么分块的方式。尤其是对于 lazytag 的更新和下放。
我瞎扯淡信不信随您啦 hhh

Code

// Code by ajcxsu
// Problem: entrance 7
#include<iostream>
#include<cstdio>
#include<cmath>
#define MOD (10007ll)
using namespace std;
typedef long long ll;

const int N=1e5+10, M=700;
ll v[N],tag[M],tag2[M];
int pos[N],bl[M],br[M];

inline void inc(ll &x, ll y) { x=(x+y)%MOD; }
inline void pl(ll &x, ll y) { x=(x*y)%MOD; }

void updblock(int x) {
    for(int i=bl[x];i<=br[x];i++)
        v[i]=(v[i]*tag2[x]+tag[x])%MOD;
    tag[x]=0, tag2[x]=1;
}

void add(int l,int r,ll c) {
    updblock(pos[l]);
    for(int i=l;i<=br[pos[l]] && i<=r;i++)
        inc(v[i],c);
    if(pos[l]!=pos[r]) {
        updblock(pos[r]);
        for(int i=r;i>=bl[pos[r]] && i>=l;i--)
            inc(v[i],c);
    }
    for(int i=pos[l]+1;i<=pos[r]-1;i++)
        inc(tag[i],c);
}

void pl(int l,int r,ll c) {
    updblock(pos[l]);
    for(int i=l;i<=br[pos[l]] && i<=r;i++)
        pl(v[i],c);
    if(pos[l]!=pos[r]) {
        updblock(pos[r]);
        for(int i=r;i>=bl[pos[r]] && i>=l;i--)
            pl(v[i],c);
    }
    for(int i=pos[l]+1;i<=pos[r]-1;i++)
        pl(tag[i],c), pl(tag2[i],c);
}



int main() {
    int n,unit,m;
    cin>>n;
    unit=sqrt(n), m=(n-1)/unit+1;
    for(int i=1;i<=n;i++) pos[i]=(i-1)/unit+1;
    for(int i=1;i<=m;i++) bl[i]=(i-1)*unit+1, br[i]=i*unit, tag2[i]=1;
    br[m]=n;
    for(int i=1;i<=n;i++) cin>>v[i];

    ll opt,a,b,c;
    for(int i=1;i<=n;i++) {
        cin>>opt>>a>>b>>c;
        if(opt==0) add(a,b,c);
        else if(opt==1) pl(a,b,c);
        else if(opt==2) cout<<(v[b]*tag2[pos[b]]+tag[pos[b]])%MOD<<endl;
    }

    return 0;
}

T8

判断块里的颜色是不是相等
然后暴力统计就行了

区间修改的话，本题同样需要使用 pushdown

早就说了复杂度是玄学（摊手）

T9

最劲爆的题
在 BZOJ 由于被 -1s 看不到

首先 $O(n\sqrt{n})$ 处理f[i][j]代表块 i 到块 j 的众数

然后用 $O(logn)$ 的时间快速查询区间 $[l,r]$ 的数的个数，原理就是把每个数离散化之后，坐标按顺序塞到 vector 里，之后如果要查某个数，则把对应的区间塞到那个数的坐标 vector 里二分。也就是说要两遍二分。

之后我们查询块时，完整块就可以直接找f[i][j]惹
但是大小还是可能会变，因此还得查一遍 $[l,r]$ 中f[i][j]的数量。
然后对于不完整的块，把里面数的数量都查一遍就 OK 了，取个最大值。
查询的复杂度最坏是 $O(4\sqrt{n}logn)$

由于降智打击 2，在下做了许多傻逼常数优化，结果发现自己是代码写错了

常数优化也不知道有没有用，反正总共跑了 1s 多的样子？

Code UPD - 2018.09.12

我写了假的离散化..
假的 LOJ 和假的初始化...

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10,M=700;
int pos[N],bl[M],br[M];
int f[M][M],fc[M][M];
int v[N];
int lis[N];

vector<int> p[N];
int tot[N];
int tim[N],rem[N],ntim;

int cnt(int l,int r,int x) {
    assert(x<N);
    if(ntim>tim[x]) tim[x]=ntim;
    else return rem[x];
    return rem[x]=upper_bound(p[x].begin(), p[x].end(), r) - lower_bound(p[x].begin(), p[x].end(), l);
}

int query(int l,int r) {
    ntim++;
    int ret=f[pos[l]+1][pos[r]-1], times=fc[pos[l]+1][pos[r]-1], nt=0;
    for(int i=l;i<=br[pos[l]] && i<=r;i++) {
        nt=cnt(l,r,v[i]);
        if((nt==times && v[i]<ret) || nt>times) times=nt, ret=v[i];
    }
    if(pos[l]!=pos[r]) {
        for(int i=r;i>=bl[pos[r]] && i>=l;i--) {
            nt=cnt(l,r,v[i]);
            if((nt==times && v[i]<ret) || nt>times) times=nt, ret=v[i];
        }
    }
    return ret;
}

inline void gn(int &x) {
    x=0;
    int t=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') t=(ch=='-'?-1:1), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
    x*=t;
}

char str[100];
inline void pn(int x) {
    register int i=0;
    while(x) str[i++]=x%10+'0', x/=10;
    while((--i)>=0) putchar(str[i]);
    putchar('\n');
}

int main() {
    int n,unit,m,q;
    gn(n), gn(q);
    unit=sqrt(n);
    m=(n-1)/unit+1;
    for(int i=1;i<=n;i++) gn(v[i]), pos[i]=(i-1)/unit+1, lis[i]=v[i];
    for(int i=1;i<=m;i++) bl[i]=br[i-1]+1, br[i]=i*unit;
    br[m]=n;
    int k;
    sort(lis+1,lis+1+n), k=unique(lis+1, lis+1+n)-lis;
    for(int i=1;i<=n;i++) v[i]=lower_bound(lis+1, lis+k, v[i])-lis;
    for(int i=1;i<=n;i++) p[v[i]].push_back(i);
    for(int i=1;i<=m;i++) {
        memset(tot,0,sizeof(tot));
        for(int j=i;j<=m;j++) {
            fc[i][j]=fc[i][j-1], f[i][j]=f[i][j-1];
            for(int k=bl[j];k<=br[j];k++) {
                tot[v[k]]++;
                if(tot[v[k]]>fc[i][j] || (tot[v[k]]==fc[i][j] && v[k]<f[i][j])) f[i][j]=v[k], fc[i][j]=tot[v[k]];
            }
        }
    }
    int l,r, lst=0;
    for(int i=1;i<=q;i++) {
        gn(l), gn(r), l=(l+lst-1)%n+1, r=(r+lst-1)%n+1;
        if(l>r) swap(l,r);
        printf("%d\n", lst=lis[query(l,r)]);
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/TLEBA-B.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆