LOJ 6277-6280 数列分块入门 1-4

时间：2021-01-13 19:39:06

数列分块是莫队分块的前置技能,练习一下

1.loj6277

给出一个长为n的数列，以及n个操作，操作涉及区间加法，单点查值。

直接分块+tag即可

#include <bits/stdc++.h>

#define ll long long

#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#define pp pair<int,int>

#define rep(ii,a,b) for(int ii=a;ii<=b;ii++)

#define per(ii,a,b) for(int ii=a;ii>=b;ii--)

using namespace std;

const int maxn=1e5+10;

const int maxm=1e6+10;

const int INF=0x3f3f3f3f;

int casn,n,m,k;

int size;

ll num[maxn],tag[maxn];

int id[maxn];

void update(int s,int t,ll x){

	for(int i=s;i<=min(id[s]*size,t);i++)

		num[i]+=x;

	if(id[s]!=id[t]){

		for(int i=(id[t]-1)*size+1;i<=t;i++)

			num[i]+=x;

	}

	for(int i=id[s]+1;i<=id[t]-1;i++){

		tag[i]+=x;

	}

}

int main(){

//#define test

#ifdef test

  freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);

#endif

	scanf("%d",&n);

	size=sqrt(n);

	for(int i=1;i<=n;i++) scanf("%lld",num+i);

	for(int i=1;i<=n;i++) id[i]=(i-1)/size+1;

	for(int i=1;i<=n;i++){

		int flag,a,b;

		ll c;

		scanf("%d%d%d%lld",&flag,&a,&b,&c);

		if(flag==0) update(a,b,c);

		else printf("%lld\n",num[b]+tag[id[b]]);

	}

#ifdef test

  fclose(stdin);fclose(stdout);system("out.txt");

#endif

  return 0;

}

　　

2.loj6278

给出一个长为n的数列，以及n个操作，操作涉及区间加法，询问区间内小于某个值x的元素个数。

分块,,用vector可以很方便得保存排序结果,每次修改两端应该重新排序

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=1e5+10;

const int maxm=1e6+10;

const int INF=0x3f3f3f3f;

int casn,n,m,k;

int size;

ll num[maxn],tag[maxn];

vector<ll>rk[maxn/100];

int id[maxn];

void reset(int pos){

	rk[pos].clear();

	for(int i=(pos-1)*size+1;i<=min(pos*size,n);i++)

		rk[pos].push_back(num[i]);

	sort(rk[pos].begin(),rk[pos].end());

}

void update(int s,int t,ll x){

	for(int i=s;i<=min(id[s]*size,t);i++)

		num[i]+=x;

	reset(id[s]);

	if(id[s]!=id[t]){

		for(int i=(id[t]-1)*size+1;i<=t;i++)

			num[i]+=x;

		reset(id[t]);

	}

	for(int i=id[s]+1;i<=id[t]-1;i++){

		tag[i]+=x;

	}

}

int query(int s,int t,ll k){

	int ans=0;

	for(int i=s;i<=min(id[s]*size,t);i++){

		if(num[i]+tag[id[s]]<k)ans++;

	}

	if(id[s]!=id[t]){

		for(int i=(id[t]-1)*size+1;i<=t;i++){

			if(num[i]+tag[id[t]]<k)ans++;

		}

	}

	for(int i=id[s]+1;i<=id[t]-1;i++){

		ans+=lower_bound(rk[i].begin(),rk[i].end(),(ll)k-tag[i])-rk[i].begin();

	}

	return ans;

}

int main(){

//#define test

#ifdef test

  freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);

#endif

	scanf("%d",&n);

	size=sqrt(n);

	for(int i=1;i<=n;i++) scanf("%lld",num+i);

	for(int i=1;i<=n;i++) {

		id[i]=(i-1)/size+1;

		rk[id[i]].push_back(num[i]);

	}

	for(int i=1;i<=n;i++)

		sort(rk[i].begin(),rk[i].end());

	for(int i=1;i<=n;i++){

		int flag,a,b;

		ll c;

		scanf("%d%d%d%lld",&flag,&a,&b,&c);

		if(flag==0) update(a,b,c);

		else printf("%d\n",query(a,b,c*c));

	}

#ifdef test

  fclose(stdin);fclose(stdout);system("out.txt");

#endif

  return 0;

}

3.loj6279

给出一个长为n的数列，以及n个操作，操作涉及区间加法，询问区间内小于某个值x的前驱（比其小的最大元素）

用多重集合维护块内元素,注意两端的部分需要重建

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=1e5+10;

const int maxm=1e6+10;

const int INF=0x3f3f3f3f;

int casn,n,m,k;

int size;

ll num[maxn],tag[maxn];

multiset<ll>vis[maxn/100];

int id[maxn];

void update(int s,int t,ll x){

	for(int i=s;i<=min(id[s]*size,t);i++){

		vis[id[s]].erase(num[i]);

		num[i]+=x;

		vis[id[s]].insert(num[i]);

	}

	if(id[s]!=id[t]){

		for(int i=(id[t]-1)*size+1;i<=t;i++){

			vis[id[t]].erase(num[i]);

			num[i]+=x;

			vis[id[t]].insert(num[i]);

		}

	}

	for(int i=id[s]+1;i<=id[t]-1;i++){

		tag[i]+=x;

	}

}

ll query(int s,int t,ll k){

	ll ans=-1;

	for(int i=s;i<=min(id[s]*size,t);i++){

		ll tmp=num[i]+tag[id[s]];

		if(tmp<k) ans=max(ans,tmp);

	}

	if(id[s]!=id[t]){

		for(int i=(id[t]-1)*size+1;i<=t;i++){

			ll tmp=num[i]+tag[id[t]];

			if(tmp<k) ans=max(ans,tmp);

		}

	}

	for(int i=id[s]+1;i<=id[t]-1;i++){

		int tmp=k-tag[i];

		multiset<ll>::iterator it=vis[i].lower_bound(tmp);

		if(it==vis[i].begin()) continue;

		--it;

		ans=max(ans,*it+tag[i]);

	}

	return ans;

}

int main(){

//#define test

#ifdef test

  freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);

#endif

	scanf("%d",&n);

	size=sqrt(n);

	for(int i=1;i<=n;i++) scanf("%lld",num+i);

	for(int i=1;i<=n;i++) {

		id[i]=(i-1)/size+1;

		vis[id[i]].insert(num[i]);

	}

	for(int i=1;i<=n;i++){

		int flag,a,b;

		ll c;

		scanf("%d%d%d%lld",&flag,&a,&b,&c);

		if(flag==0) update(a,b,c);

		else printf("%d\n",query(a,b,c));

	}

#ifdef test

  fclose(stdin);fclose(stdout);system("out.txt");

#endif

  return 0;

}

4.loj6280

给出一个长为n的数列，以及n个操作，操作涉及区间加法，区间求和。

直接分块,同时需要维护一个块元素和

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=1e5+10;

const int maxm=1e6+10;

const int INF=0x3f3f3f3f;

int casn,n,m,k;

int size;

ll num[maxn],tag[maxn],sum[maxn];

int id[maxn];

void update(int s,int t,ll x){

	for(int i=s;i<=min(id[s]*size,t);i++){

		num[i]+=x;

	}

	sum[id[s]]+=x*(min(id[s]*size,t)-s+1);

	if(id[s]!=id[t]){

		for(int i=(id[t]-1)*size+1;i<=t;i++){

			num[i]+=x;

		}

		sum[id[t]]+=(t-(id[t]-1)*size)*x;

	}

	for(int i=id[s]+1;i<=id[t]-1;i++){

		tag[i]+=x;

	}

}

ll query(int s,int t){

	ll ans=0;

	for(int i=s;i<=min(id[s]*size,t);i++){

		ans+=num[i]+tag[id[s]];

	}

	if(id[s]!=id[t]){

		for(int i=(id[t]-1)*size+1;i<=t;i++){

			ans+=num[i]+tag[id[t]];

		}

	}

	for(int i=id[s]+1;i<=id[t]-1;i++){

		ans+=sum[i]+tag[i]*size;

	}

	return ans;

}

int main(){

//#define test

#ifdef test

  freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);

#endif

	scanf("%d",&n);

	size=sqrt(n);

	for(int i=1;i<=n;i++) scanf("%lld",num+i);

	for(int i=1;i<=n;i++) {

		id[i]=(i-1)/size+1;

		sum[id[i]]+=num[i];

	}

	for(int i=1;i<=n;i++){

		int flag,a,b;

		ll c;

		scanf("%d%d%d%lld",&flag,&a,&b,&c);

		if(flag==0) update(a,b,c);

		else printf("%lld\n",query(a,b)%(c+1));

	}

#ifdef test

  fclose(stdin);fclose(stdout);system("out.txt");

#endif

  return 0;

}

(其实LOJ的题目数据比较水,欢迎hack我)

相关文章