区间分块的两道例题

发表于 更新于 分类于 ， 阅读次数：

今日闲来无事乱翻刷题清单，看见分块这个专题，想起最近频频听人提起，便心血来潮学一波。
区间分块十分好学，二十分钟就大概弄清楚基础操作。
主要应用于一些区间离奇修改，线段树不好写的情况。
核心思想是将长度为n的区间分割为长度为$\sqrt{n}$的$\sqrt{n}$​区间。
写出构建、修改、查询三个函数就可以了。

区间反转

P3870 [TJOI2009]开关

题意

一排n盏灯，初始都灭。按输入执行以下两种操作

  • 操作指定一个区间[a, b]，然后改变编号在这个区间内的灯的状态
  • 指定一个区间[a, b]，要求你输出这个区间内有多少盏灯是打开的

思路

要求支持区间反转和区间查询，在线操作。
因为区间修改会耗费大量时间，当整个$\sqrt{n}$区间都被修改时，添加lazy标签，不进行单个灯的修改。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int maxm=1005;
int num,siz,belong[maxn];//分块数量和大小,表示i属于哪一块
bool d[maxn];
struct block
{
    int l,r,light;
    bool lazy;
    block()
    {
        l=r=light=0;//第i块有多少灯在亮
        lazy=0;//0表示还未反转
    }
} bl[maxm];
inline int read()//快读挂
{
    int x=0,f=1;//改动x%mod即可在读入时取模
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return x*f;
}
inline void out(register int x)
{
    if(x>=10)
        out(x/10);
    putchar(x%10+'0');
}
void build(int n)
{
    siz=sqrt(n);
    num=n/siz;
    if(num%siz)
        num++;
    for(int i=1;i<=num;i++)
        bl[i].l=(i-1)*siz+1,bl[i].r=i*siz;
    bl[num].r=n;//特殊处理
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/siz+1;
}
void debug(int n)
{
    printf("lazy:\t");
    for(int i=1;i<=n;i++)
        printf("%4d",bl[belong[i]].lazy);
    printf("\n");
    printf("d:\t");
    for(int i=1;i<=n;i++)
        printf("%4d",d[i]);
    printf("\nans:\t");
    for(int i=1;i<=n;i++)
        printf("%4d",bl[belong[i]].light);
    printf("\n****\n");
}
void modify(int l,int r)
{
    if(belong[l]==belong[r])//在同一块内
    {
        for(int i=l;i<=r;i++)
        {//有r-l+1盏灯,暴力修改
            if(d[i])
            {
                if(!bl[belong[i]].lazy)//灯在亮且本块未标记修改
                    bl[belong[i]].light--;
                else
                    bl[belong[i]].light++;
            }
            else{
//                printf("???");
                if(!bl[belong[i]].lazy)//灯灭且区间未标记修改
                    bl[belong[i]].light++;
                else
                    bl[belong[i]].light--;//灯灭且区间标记已修改
            }
            d[i]^=1;//散装灯的状态还是要修改的...
        }
//        debug(5);
        return;
    }
    //否则不在同一块
    for(int i=l;i<=bl[belong[l]].r;i++)
    {
        if(d[i])
        {
            if(!bl[belong[i]].lazy)//灯在亮且本块未标记修改
                bl[belong[i]].light--;
            else
                bl[belong[i]].light++;
        }
        else{
            if(!bl[belong[i]].lazy)//灯灭且区间未标记修改
                bl[belong[i]].light++;
            else
                bl[belong[i]].light--;//灯灭且区间标记已修改
        }
        d[i]^=1;
    }
    for(int i=belong[l]+1;i<belong[r];i++)//整块的修改lazy标记
    {
        bl[i].lazy^=1;
        bl[i].light=siz-bl[i].light;
    }
    for(int i=bl[belong[r]].l;i<=r;i++)
    {
        if(d[i])
        {
            if(!bl[belong[i]].lazy)//灯在亮且本块未标记修改
                bl[belong[i]].light--;
            else
                bl[belong[i]].light++;
        }
        else{
            if(!bl[belong[i]].lazy)//灯灭且区间未标记修改
                bl[belong[i]].light++;
            else
                bl[belong[i]].light--;//灯灭且区间标记已修改
        }
        d[i]^=1;
    }
}
int query(int l,int r)
{
    if(belong[l]==belong[r])//在同一块内
    {
        int cnt=0;
        for(int i=l;i<=r;i++)
            if(d[i]^bl[belong[i]].lazy)
                cnt++;
        return cnt;
    }
    int ans=0;//不在同一块
    for(int i=l;i<=bl[belong[l]].r;i++)
        if(d[i]^bl[belong[i]].lazy)
            ans++;
    for(int i=belong[l]+1;i<belong[r];i++)
        ans+=bl[i].light;
    for(int i=bl[belong[r]].l;i<=r;i++)
        if(d[i]^bl[belong[i]].lazy)
            ans++;
    return ans;
}
int main()
{
    int n,m,ope,a,b;
    n=read(),m=read();
    build(n);
    while(m--)
    {
        ope=read(),a=read(),b=read();
        if(ope==0)
            modify(a,b);
        else
            out(query(a,b)),putchar('\n');
    }
    return 0;
}

区间众数

P4168 [Violet]蒲公英

题意

给定区间，求出这段区间的众数，强制在线。
本题不爆int，但有点卡常，套了个快读板子……

做法

因为种类（所给的数）过大，要先离散化。
但可以通过map和记录id对应的val同样区分种类和相对大小，并且好写，我就这么干了QwQ。
其实是我太菜了不会离散化
同时开一个$vector$数组$pos$，$pos[x]$记录编号为$x$的蒲公英所有的出现位置，通过STL函数来二分查找一个区间内x出现的次数。
$f[i][j]$表示第i块到第j块的众数，在查询之前先预处理出来。
注意要一开始就更新$ans$和$maxc$。
然后枚举询问$[l,r]$左面和右面散装蒲公英的种类，在整个区间内查询该种类的数量，与$maxc$进行比较并记录最大值即可。
在$query$里面暴力写写写就好了。

AC的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()//快读挂
{
    int x=0,f=1;//改动x%mod即可在读入时取模
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return x*f;
}
inline void out(register int x)
{
    if(x>=10)
        out(x/10);
    putchar(x%10+'0');
}
const int maxn=40005,lim=205,inf=0x3f3f3f3f;
int a[maxn],c[maxn],id=0,f[lim][lim];
int siz,num,belong[maxn];
struct block
{
    int l,r;
} b[lim];
map<int,int> QAQ;
vector<int> pos[maxn];//存储种类下标
int val[maxn];//QAQ的反函数
void debug(int n)
{
    printf("siz=%d,num=%d\n",siz,num);
    for(int i=1;i<=num;i++)
    {
        for(int j=i;j<=num;j++)
        {
            printf("f[%d][%d]=%d\n",i,j,f[i][j]);
        }
    }
}
void build(int n)
{
    siz=sqrt(n);
    num=n/siz;
    if(n%siz)
        num++;
    for(int i=1;i<=num;i++)
        b[i].l=(i-1)*siz+1,b[i].r=i*siz;
    b[num].r=n;//特殊处理
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/siz+1;
    //伪离散化
//    for(int i=1;i<=n;i++)
//        pos[i].push_back(-1);
    for(int i=1;i<=n;i++)
    {
        if(QAQ[a[i]]==0)
        {
            QAQ[a[i]]=++id;//新编号
            val[id]=a[i];
//            printf("val[%d]=%d,QAQ[%d]=%d\n",id,val[id],a[i],QAQ[i]);
        }
        a[i]=QAQ[a[i]];
        pos[a[i]].push_back(i);//记录出现位置,自动升序
    }
    //暴力预处理区间众数,f[i][j]表示i块到j块*众数编号*
    for(int i=1;i<=belong[n];i++)
    {
        memset(c,0,sizeof(c));
        int maxc=0,ans=0;
        for(int j=b[i].l;j<=n;j++)//枚举起点,一直处理到最后
        {
            c[a[j]]++;//统计数量
            if(c[a[j]]>maxc||c[a[j]]==maxc&&val[a[j]]<val[ans])
            {//更新当前众数答案
                maxc=c[a[j]];//更新众数数量
                ans=a[j];
            }
            f[i][belong[j]]=ans;
//            printf("a[%d]=%d,c=%d\n",j,a[j],c[a[j]]);
//            printf("f[%d][%d]=%d\n",i,belong[j],f[i][belong[j]]);
        }
    }
//    debug(n);
}
int querynum(int l,int r,int x)//查询[l,r]内编号为x的数量
{
    return upper_bound(pos[x].begin(),pos[x].end(),r)-lower_bound(pos[x].begin(),pos[x].end(),l);
}
int query(int l,int r)
{
    int ans=0,maxc=0;
    ans=f[belong[l]+1][belong[r]-1];//提溜出来中间的整块众数
    maxc=querynum(l,r,ans);
    if(belong[l]==belong[r])
    {
//        memset(c,0,sizeof(c));
        for(int i=l;i<=r;i++)
        {
            int num=querynum(l,r,a[i]);//查询a[i]在[l,r]上的个数
            if(num>maxc||num==maxc&&val[a[i]]<val[ans])
            {
//                printf("ans=%d,maxc=%d\n",ans,maxc);
                ans=a[i];
                maxc=num;
            }
        }
        return val[ans];
    }
    //不在同一块
//    printf("ans=%d,maxc=%d\n",ans,maxc);
    for(int i=l;i<=b[belong[l]].r;i++)//枚举左面散装
    {
        int num=querynum(l,r,a[i]);//查询a[i]在[l,r]上的个数
        if(num>maxc||num==maxc&&val[a[i]]<val[ans])
        {
//            printf("ans=%d,maxc=%d\n",ans,maxc);
            ans=a[i];
            maxc=num;
        }
    }
    for(int i=b[belong[r]].l;i<=r;i++)
    {
        int num=querynum(l,r,a[i]);//查询a[i]在[l,r]上的个数
        if(num>maxc||num==maxc&&val[a[i]]<val[ans])
        {
            ans=a[i];
            maxc=num;
        }
//        printf("a[%d]=%d,ans=%d,maxc=%d\n",i,a[i],ans,maxc);
    }
//    printf("ans=%d,maxc=%d\n",ans,maxc);
    return val[ans];//返回实际种类
}
signed main()
{
//    freopen("P4168.in","r",stdin);
    int n,m,ans=0;//n株蒲公英,m次询问
//    scanf("%d%d",&n,&m);
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    build(n);
    while(m--)
    {
        int l0,r0,l,r;
//        scanf("%d%d",&l0,&r0);
        l0=read(),r0=read();
        l=(l0+ans-1)%n+1;
        r=(r0+ans-1)%n+1;
        if(l>r)
            swap(l,r);
        ans=query(l,r);
        printf("%d\n",ans);
    }
    return 0;
}

2019年12月4日22点48分