• 数列分块入门

    分块的思想在于将一个区间分成多块，利用整块处理的方式来提高程序运行的速度。分块十分灵活能够解决多种问题，这些问题有些线段树可以解决，但有些不能，作为灵活性的代价，其效率会比线段树低一些，而且复杂度算不对会T。

    比方说，我们选择l到r区间，这个区间包含了完整的3个大小为size的块，那么我们对这个块的操作通常是O(1)级别的操作。

    当然，我们选定的区间通常并非恰好是某些块的端点，也没法将数组正好分成k块每块的都是size大小，所以处理这些边界数据的问题变成了主要的时间耗费。

    想要处理起来容易，就需要前期工作准备充分一些。
    1.对于块，开一个结构体，存储一个块的内部元素，这个块在原数组中的起始于终止下标，这个块的长度，这个块的各种tag，等等信息都可以存储。这样做的好处是对于每一块，块内元素处理起来十分方便。
    2.对于每个元素，我们要预处理其属于那一块。
    3.关于块的大小，玄学，，一般情况下如果数组大小为n，求出其sqrt(n)，找到距离sqrt(n)最近的2的幂数就可以了。如果T了可以尝试将块缩小两倍（优先）或者增大两倍。

    大体思路

    基本都分为两步走
    1.如果所查询的区间在一个块的范围内，那么直接暴力遍历从l到r
    2.如果跨越多个块，先将整块整块的处理完，再处理边角区间

    入门题目

    这里主要包括一些基本数列分块题目，第一题由于过于简单所以没用我的模板，第2题到第8题都是模板下来的。第九题因为变化较大，模板不太适合所以没用模板。

    这些题目我感觉都很好，作为数列分块的题目来讲，很基础也很全面，难度大概是luogu的绿到蓝

    以下题目の测评地址与题目地址

    第1题

    请添加图片描述

    可以看到，这题需要记录一下区间的累加值，在求值的时候可以直接加上区间的累加值。

    先看代码吧。

    #include
using namespace std;
const int N=5e4+5;
typedef long long ll;
int n,len,id[N];
ll a[N],tag[N];
void add(int l,int r,ll c)
{
	int sid=id[l],eid=id[r];
	if(sid==eid)
		for(int i=l;i<=r;i++)
			a[i]+=c;
	else
	{
		for(int i=l;id[i]==sid;i++) a[i]+=c;
		for(int i=sid+1;i<eid;i++) tag[i]+=c;
		for(int i=r;id[i]==eid;i--) a[i]+=c;
	}
}
int main()
{
	ll c;
	scanf("%d",&n);
	len=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		id[i]=(i-1)/len+1;
	}
	for(int i=1,opt,x,y;i<=n;i++)
	{
		scanf("%d%d%d%lld",&opt,&x,&y,&c);
		if(!opt)
			add(x,y,c);
		else
			printf("%lld\n",a[y]+tag[id[y]]);
	}
	return 0;
}

    • 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

    关于为什么求x位置的数直接输出x+所属块的累加值即可。
    这个其实原因是在upd函数上，当我们发现操作区间是整块的时，我们不操作具体每一个元素，仅仅是标记一下，但是没有跨越整块区间则是具体操作每个数值，所以累加值就是这个数值相应的应该加的值。

    第2题

    在这里插入图片描述
    这题就是经典的计数问题了，只需要获取每个元素当前值然后对比就可以了，是第一个题目的进阶，注意c2需要用longlong表示。

    #include
using namespace std;
const int N = 1e5+100;
typedef long long ll;
ll a[N];//原数组
int along[N];//注册每个元素属于那一块
int n;
const int block=300;//sqrt(n)块，一块有n/sqrt(n)个
struct node//存储了每一块的起点，终点，长度，
{
	ll st,ed,length,add,num[block+10];
	void change(){
		for(int i=st;i<=ed;i++)num[i-st+1]=a[i];
		sort(num+1,num+length+1);
	}
	int ask(ll c)
	{
		return lower_bound(num+1,num+length+1,c-add)-num-1;
	}
}b[block];
void upd(int l,int r,int v)
{
	int p=along[l],q=along[r];
	if(p==q){
		for(int i=l;i<=r;i++)a[i]+=v;
		b[p].change();
		return;
	}
	for(int i=p+1;i<=q-1;i++)b[i].add+=v;
	for(int i=l;i<=b[p].ed;i++)a[i]+=v;
	for(int i=b[q].st;i<=r;i++)a[i]+=v;
	b[p].change();
	b[q].change();
}
int query(int l,int r,ll c)
{
	int ret=0;
	int p=along[l],q=along[r];
	if(p==q)
    {
		for(int i=l;i<=r;i++)
		if(a[i]+b[p].add<c)ret++;
		return ret;
	}
	for(int i=p+1;i<=q-1;i++)ret+=b[i].ask(c);
	for(int i=l;i<=b[p].ed;i++)
	if(a[i]+b[p].add<c)ret++;
	for(int i=b[q].st;i<=r;i++)
	if(a[i]+b[q].add<c)ret++;
	return ret;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	int t=n/block;
	if(n%block)t++;
	for(int i=1;i<=t;i++)
    {
		b[i].st=(i-1)*block+1;
		b[i].ed=i*block;
		b[i].length=b[i].ed-b[i].st+1;
	}
	b[t].ed=n;
	b[t].length=n-b[t].st+1;
	for(int i=1;i<=t;i++)
    {
		b[i].change();
		for(int j=b[i].st;j<=b[i].ed;j++)
		along[j]=i;
	}
	for(int i=1;i<=n;i++)
    {
		int op,l,r;
		ll c;
		cin>>op>>l>>r>>c;
		if(op)cout<<query(l,r,c*c)<<'\n';
		else upd(l,r,c);
	}
	return 0;
}

    • 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

    第3题

    请添加图片描述
    题目的修改操作仍为区间加值，

    对于整块的区间，查询块内c的前驱，只需要查询比c小的最大值排在第几个就可以了。

    对于分散的区间，只需要查询比c小的最大值（打擂台）

    #include
using namespace std;
#define int long long
const int N = 2e5+100;
int a[N];//原数组
int along[N];//注册每个元素属于那一块
int n;
const int block=500;//sqrt(n)块，一块有n/sqrt(n)个
struct node//存储了每一块的起点，终点，长度，这个区间被加了多少值，区间内的元素
{
	int st,ed,length,add=0ll,num[block+10];
	void change(){
		for(int i=st;i<=ed;i++)num[i-st+1]=a[i];
		sort(num+1,num+length+1);
	}
	int ask(int c)
	{
		int pos=lower_bound(num+1,num+length+1,c-add)-(num+1);
		if(!pos)
            return -1;
        return num[pos]+add;
	}
}b[block];

void upd(int l,int r,int v)
{
	int p=along[l],q=along[r];
	if(p==q)
    {
		for(int i=l;i<=r;i++)a[i]+=v;
		b[p].change();
		return;
	}
	for(int i=p+1;i<=q-1;i++)b[i].add+=v;
	for(int i=l;i<=b[p].ed;i++)a[i]+=v;
	for(int i=b[q].st;i<=r;i++)a[i]+=v;
	b[p].change();
	b[q].change();
}
int query(int l,int r,int c)
{
    int res=-1;
	int p=along[l],q=along[r];
	if(p==q)
    {
		for(int i=l;i<=r;i++)
		if((a[i]+b[q].add)<c)
            res=max(res,a[i]+b[p].add);
		return res;
	}
	for(int i=p+1;i<=q-1;i++)
    {
        res=max(res,b[i].ask(c));
    }
	for(int i=l;i<=b[p].ed;i++)
	{
	    if((a[i]+b[p].add)<c)
            res=max(res,a[i]+b[p].add);
	}
	for(int i=b[q].st;i<=r;i++)
	{
	    if((a[i]+b[q].add)<c)
            res=max(res,a[i]+b[q].add);
	}
	return res;
}
signed main()
{
    //freopen("in.txt","r",stdin);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	int t=n/block;
	if(n%block)t++;
	for(int i=1;i<=t;i++)
    {
		b[i].st=(i-1)*block+1;
		b[i].ed=i*block;
		b[i].length=b[i].ed-b[i].st+1;
	}
	b[t].ed=n;
	b[t].length=n-b[t].st+1;
	for(int i=1;i<=t;i++)
    {
		b[i].change();
		for(int j=b[i].st;j<=b[i].ed;j++)
		along[j]=i;
	}
	for(int i=1;i<=n;i++)
    {
		int op,l,r;
		int c;
		cin>>op>>l>>r>>c;
		if(op)
        {
            cout<<query(l,r,c)<<'\n';
        }
		else upd(l,r,c);
	}
	return 0;
}

    • 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

    第4题

    请添加图片描述
    我们记录区间的sum标记，和add标记，分别代表：目前的和，待加数。那么对于一个整块的区间的区间和就是sum+add*block

    对于分散的区间自然逐个加和即可。

    #include
using namespace std;
#define int long long
const int N = 2e5+100;
int a[N];//原数组
int along[N];//注册每个元素属于那一块
int n;
const int block=300;//sqrt(n)块，一块有n/sqrt(n)个
struct node//存储了每一块的起点，终点，长度，这个区间被加了多少值，区间内的元素
{
	int st,ed,length,add=0,num[block+10],sum=0;
    void change()
	{
		for(int i=st;i<=ed;i++)
        {
            sum+=(a[i]-num[i-st+1]);
            num[i-st+1]=a[i];
        }
	}
	int ask(int c)
	{
		int pos=lower_bound(num+1,num+length+1,c-add)-(num+1);
		if(!pos)
            return -1;
        return num[pos]+add;
	}
}b[block];

void upd(int l,int r,int v)
{
	int p=along[l],q=along[r];
	if(p==q)
    {
		for(int i=l;i<=r;i++)a[i]+=v;
		b[p].change();
		return;
	}
	for(int i=p+1;i<=q-1;i++)b[i].add+=v;
	for(int i=l;i<=b[p].ed;i++)a[i]+=v;
	for(int i=b[q].st;i<=r;i++)a[i]+=v;
	b[p].change();
	b[q].change();
}
int query(int l,int r,int c)
{
    int res=0;
	int p=along[l],q=along[r];
	if(p==q)
    {
        for(int i=l;i<=r;i++)
        {
            res=(res+a[i]+b[p].add)%c;
        }
        return res;
	}
	for(int i=p+1;i<=q-1;i++)
    {
        res=(res%c+b[i].sum%c+b[i].add*block%c)%c;
    }
	for(int i=l;i<=b[p].ed;i++)
	{
	    res=(res+a[i]+b[p].add)%c;
	}
	for(int i=b[q].st;i<=r;i++)
	{
	    res=(res+a[i]+b[q].add)%c;
	}
	return res%c;
}
signed main()
{
    //freopen("in.txt","r",stdin);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	int t=n/block;
	if(n%block)t++;
	for(int i=1;i<=t;i++)
    {
		b[i].st=(i-1)*block+1;
		b[i].ed=i*block;
		b[i].length=b[i].ed-b[i].st+1;
	}
	b[t].ed=n;
	b[t].length=n-b[t].st+1;

	for(int i=1;i<=t;i++)
    {
		b[i].change();
		for(int j=b[i].st;j<=b[i].ed;j++)
		along[j]=i;
	}

	for(int i=1;i<=n;i++)
    {
		int op,l,r;
		int c;
		cin>>op>>l>>r>>c;
		if(op)
        {
            cout<<query(l,r,c+1)<<'\n';
        }
		else upd(l,r,c);
	}
	return 0;
}


    • 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

    第5题

    请添加图片描述
    关键在于更新操作上。

    #include
using namespace std;
#define int long long
const int N = 2e5+100;
int a[N];//原数组
int along[N],vis[N];//注册每个元素属于那一块
int n;
const int block=300;//sqrt(n)块，一块有n/sqrt(n)个
struct node//存储了每一块的起点，终点，长度，这个区间被加了多少值，区间内的元素
{
	int st,ed,length,num[block+10],sum=0ll,id;
}b[block];

void upd(int l,int r,int v)
{
	int p=along[l],q=along[r];
	if(p==q)
    {
		for(int i=l;i<=r;i++)
        {
            if(a[i]>1)
            {
                b[q].sum-=a[i];
                a[i]=sqrt(a[i]);
                b[q].sum+=a[i];
            }
        }
		return;
	}
	for(int i=p+1;i<=q-1;i++)
    {
        if(vis[i])
        {
            for(int j=b[i].st;j<=b[i].ed;j++)
            {
                if(a[j]>1)
                {
                    b[i].sum-=a[j];
                    a[j]=sqrt(a[j]);
                    b[i].sum+=a[j];
                }
            }
            if(b[i].sum==b[i].length)
                vis[i]=0;
        }
    }
	for(int i=l;i<=b[p].ed;i++)
    {
        if(a[i]>1)
        {
            b[p].sum-=a[i];
            a[i]=sqrt(a[i]);
            b[p].sum+=a[i];
        }
    }
	for(int i=b[q].st;i<=r;i++)
    {
        if(a[i]>1)
        {
            b[q].sum-=a[i];
            a[i]=sqrt(a[i]);
            b[q].sum+=a[i];
        }
    }
}
int query(int l,int r)
{
    int res=0;
	int p=along[l],q=along[r];
	if(p==q)
    {
        for(int i=l;i<=r;i++)
            res+=a[i];
        return res;
	}
	for(int i=p+1;i<=q-1;i++)
    {
        res+=b[i].sum;
    }
	for(int i=l;i<=b[p].ed;i++)
	{
        res+=a[i];
	}
	for(int i=b[q].st;i<=r;i++)
	{
	    res+=a[i];
	}
	return res;
}
signed main()
{
    //freopen("in.txt","r",stdin);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
	    cin>>a[i];
	}
	int t=n/block;
	if(n%block)t++;
	for(int i=1;i<=t;i++)
    {
		b[i].st=(i-1)*block+1;
		b[i].ed=i*block;
		b[i].length=b[i].ed-b[i].st+1;
		vis[i]=1;
	}
	b[t].ed=n;
	b[t].length=n-b[t].st+1;

	for(int i=1;i<=t;i++)
    {
		for(int j=b[i].st;j<=b[i].ed;j++)
		{
		    b[i].sum+=a[j];
		    along[j]=i;
		}
	}

	for(int i=1;i<=n;i++)
    {
		int op,l,r;
		int c;
		cin>>op>>l>>r>>c;
		if(op)
        {
            cout<<query(l,r)<<'\n';
        }
		else upd(l,r,c);
	}
	return 0;
}


    • 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

    第6题

    请添加图片描述

    双修改，这里就和线段树的双tag很像了。要考虑不同修改的优先值和相互之间的影响。

    而且，这个题因为双修改，目前的值如果变动必须要把附加在当前值上的操作都做完才行，也就是对应的pushdown操作，有兴趣的可以用分块去挑战一下luogu上的“扶苏的问题”

    #include
using namespace std;
#define int long long
const int N = 2e5+100;
const int mod= 1e4+7;
int a[N];//原数组
int along[N];//注册每个元素属于那一块
int n;
const int block=400;//sqrt(n)块，一块有n/sqrt(n)个
struct node//存储了每一块的起点，终点，长度，这个区间被加了多少值，区间内的元素
{
	int st,ed,length,add=0ll,ploy=1ll,num[block+10],sum=0;
}b[block];
void down(int k)
{
    for(int i=b[k].st;i<=b[k].ed;i++)
        a[i]=(a[i]*b[k].ploy+b[k].add)%mod;
    b[k].ploy=1ll;b[k].add=0ll;
}
void upd_add(int l,int r,int v)
{
	int p=along[l],q=along[r];
	if(p==q)
    {
        down(p);
		for(int i=l;i<=r;i++)
            a[i]=(a[i]+v)%mod;
		return;
	}
	down(p);down(q);
	for(int i=p+1;i<=q-1;i++)
        b[i].add=(b[i].add+v)%mod;
	for(int i=l;i<=b[p].ed;i++)
        a[i]=(a[i]+v)%mod;
	for(int i=b[q].st;i<=r;i++)
        a[i]=(a[i]+v)%mod;
}
void upd_ploy(int l,int r,int v)
{
    int p=along[l],q=along[r];
    if(p==q)
    {
        down(p);
        for(int i=l;i<=r;i++)
            a[i]=a[i]*v%mod;
        return ;
    }
    down(p);down(q);
    for(int i=p+1;i<=q-1;i++)
    {
        b[i].ploy=b[i].ploy*v%mod;
        b[i].add=b[i].add*v%mod;
    }
    for(int i=l;i<=b[p].ed;i++)
        a[i]=a[i]*v%mod;
    for(int i=b[q].st;i<=r;i++)
        a[i]=a[i]*v%mod;
    return ;
}
int query(int r)
{
    int p=along[r];
    return a[r]*b[p].ploy+b[p].add;
}
signed main()
{
    //freopen("in.txt","r",stdin);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	int t=n/block;
	if(n%block)t++;
	for(int i=1;i<=t;i++)
    {
		b[i].st=(i-1)*block+1;
		b[i].ed=i*block;
		b[i].length=b[i].ed-b[i].st+1;
	}
	b[t].ed=n;
	b[t].length=n-b[t].st+1;

	for(int i=1;i<=t;i++)
    {
		for(int j=b[i].st;j<=b[i].ed;j++)
		along[j]=i;
	}
	for(int i=1;i<=n;i++)
    {
		int op,l,r;
		int c;
		cin>>op>>l>>r>>c;
		if(op==0)
        {
            upd_add(l,r,c);
        }
        else if(op==1)
        {
            upd_ploy(l,r,c);
        }
        else
        {
            cout<<query(r)%mod<<endl;
        }
	}
	return 0;
}

    • 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

    第7题

    请添加图片描述
    同样是目前值修改需要考虑之前的影响。也有可以不考虑的巧妙写法，读者可以挑战一下。

    #include
using namespace std;
#define int long long
const int N = 2e5+100;
const int sp= 1e10+7;
int a[N];//原数组
int along[N];//注册每个元素属于那一块
int n;
int vis[N];
const int block=400;//sqrt(n)块，一块有n/sqrt(n)个
struct node//存储了每一块的起点，终点，长度，这个区间被加了多少值，区间内的元素
{
	int st,ed,length,vis=0ll,num[block+10],bec;
}b[block];
void down(int k)
{
    if(b[k].vis)
    for(int i=b[k].st;i<=b[k].ed;i++)
        a[i]=b[k].bec;
    b[k].vis=0;
}
int upd_query(int l,int r,int c)
{
    int p=along[l],q=along[r];
    int ans=0ll;
    if(p==q)
    {
        down(p);
        for(int i=l;i<=r;i++)
        {
            ans+=(a[i]==c);
            a[i]=c;
        }
        return ans;
    }
    down(p);down(q);
    for(int i=p+1;i<=q-1;i++)
    {
        if(b[i].vis)
            ans+=((b[i].bec==c)*b[i].length);
        else
            for(int j=b[i].st;j<=b[i].ed;j++)
                ans+=(a[j]==c);
        b[i].vis=1,b[i].bec=c;
    }
    for(int i=l;i<=b[p].ed;i++)
    {
        ans+=(a[i]==c);
        a[i]=c;
    }
    for(int i=b[q].st;i<=r;i++)
    {
        ans+=(a[i]==c);
        a[i]=c;
    }
    return ans;
}
signed main()
{
    //freopen("in.txt","r",stdin);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	int t=n/block;
	if(n%block)t++;
	for(int i=1;i<=t;i++)
    {
		b[i].st=(i-1)*block+1;
		b[i].ed=i*block;
		b[i].length=b[i].ed-b[i].st+1;
	}
	b[t].ed=n;
	b[t].length=n-b[t].st+1;

	for(int i=1;i<=t;i++)
    {
		for(int j=b[i].st;j<=b[i].ed;j++)
		along[j]=i;
	}
	for(int i=1,c,l,r;i<=n;i++)
    {
		cin>>l>>r>>c;
		cout<<upd_query(l,r,c)<<'\n';
	}
	return 0;
}


    • 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

    第8题

    请添加图片描述
    这题和之前的题思路上有根本的不同，需要预处理一个dp[i][j]表示第i块到第j块的众数。
    具体操作看代码大概就能懂了。

    #include
#define int long long
using namespace std;
const int N = 1e5+100;
const int block=100;
const int NN= 1e3+100;
int n,id,v[N],belong[N],dp[NN][NN];//第i块到第j块的众数。
map<int,int>mp;
int val[N],cnt[N];
vector<int>ve[N];
void pre(int x)
{
    memset(cnt,0,sizeof(cnt));
    int mx=0,ans=0;
    for(int i=(x-1)*block+1;i<=n;i++)
    {
        cnt[v[i]]++;
        if(cnt[v[i]]>mx||(cnt[v[i]]==mx&&val[v[i]]<val[ans]))
        {
            ans=v[i];
            mx=cnt[v[i]];
        }
        dp[x][belong[i]]=ans;
    }
}

int query(int l,int r,int x)//求出在l到r范围内有几个ans
{
    int t=upper_bound(ve[x].begin(),ve[x].end(),r)-lower_bound(ve[x].begin(),ve[x].end(),l);
    return t;
}

int query(int a,int b)
{
    int ans=0,mx=0;
    ans=dp[belong[a]+1][belong[b]-1];
    mx=query(a,b,ans);
    for(int i=a;i<=min(belong[a]*block,b);i++)
    {
        int t=query(a,b,v[i]);
        if(t>mx||(t==mx&&val[v[i]]<val[ans]))
        {
            ans=v[i];
            mx=t;
        }
    }
    if(belong[a]!=belong[b])
        for(int i=(belong[b]-1)*block+1;i<=b;i++)
        {
            int t=query(a,b,v[i]);
            if(t>mx||(t==mx&&val[v[i]]<val[ans]))
            {
                ans=v[i];
                mx=t;
            }
        }
    return ans;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
        if(!mp[v[i]])
        {
            mp[v[i]]=++id;
            val[id]=v[i];
        }
        v[i]=mp[v[i]];
        ve[v[i]].push_back(i);
    }
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=belong[n];i++)
        pre(i);
    for(int i=1,a,b;i<=n;i++)
    {
        cin>>a>>b;
        if(a>b)
        swap(a,b);
        cout<<val[query(a,b)]<<endl;
    }
    return 0;
}

    • 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

    入门共9题，有一题未展示，共写了52发之后全A。

  • 相关阅读:
    「学习笔记」线段树标记永久化
    归并排序（C）递归与分治策略
    Java学习 --- hashCode、toString、finalize方法
    hive on spark 记录
    相机内外参实践之点云投影矢量图
    SystemV 信号量（一） —— SystemV信号量的相关操作函数
    企业运维实践-还不会部署高可用的kubernetes集群?使用kubeadm方式安装高可用k8s集群v1.23.7
    只要一个软件，就能满足移动数据分析的所有需求！
    策略+枚举 优雅的消灭 if-else
    〖Python 数据库开发实战 - MySQL篇⑰〗- 聚合函数的使用
  • 原文地址：https://blog.csdn.net/qq_35866893/article/details/126550486