OI康复计划

好久好久没有碰oi然而9月19日有一个CSP的认证考试,强行被拉回来搞oi orz orz orz.....

目前是准备刷csp真题+codeforces+atcoder+刷模板题同时搞0.0


 

分块算法

分成一块一块处理,当处理区间问题,左右小区块暴力处理,中间被分到的大区块整块整块处理。复杂度 O(n根号n)

luoguP3372 【模板】线段树 1

分块处理即可(没过的假代码理解思想就好)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
const int maxn = 200005;
ll n,m,fk,ks;
ll sm[maxn],lz[maxn];
ll a[maxn];
ll bl[maxn];
void pt(ll x) {
	printf("%lld\n",x);
}
int main(){
    scanf("%lld%lld",&n,&m);
    fk = pow(n,0.5);
    for(ll i=1;i<=n;i++) {
        bl[i] = bl[i-1];
        if(i%fk==1) bl[i]++;
        scanf("%lld",&a[i]);
        sm[bl[i]]+=(ll)a[i];
    }
	ll op,x,y;ll k;
	while(m--) {
		scanf("%lld%lld%lld",&op,&x,&y);
		if(op==1) {
			scanf("%lld",&k);
			if(bl[x]!=bl[y]) {
				for(int i=x;i<=bl[x]*fk;i++) a[i]+=k,sm[bl[x]]+=k;
				for(int i=y;i>=(bl[y]-1)*fk+1;i--) a[i]+=k,sm[bl[y]]+=k;
				for(int i=bl[x]+1;i<=bl[y]-1;i++) lz[i]+=k,sm[i]+=(ll)k*fk;
			} else {
				for(int i=x;i<=y;i++) a[i] += k;
				sm[bl[x]] += (ll)(y-x+1)*k;
			}
		} else {
			if(bl[x]==bl[y]) {
				ll su = (ll)lz[bl[x]]*(y-x+1);
				for(int i=x;i<=y;i++) {
					su += a[i];
				}
				pt(su);
			} else {
				ll su = 0;
				for(int i=x;i<=bl[x]*fk;i++) {
					su += a[i] + lz[bl[x]];
				}
				for(int i=y;i>=(bl[y]-1)*fk+1l;i--) {
					su += a[i] + lz[bl[y]];
				}
				for(int i=bl[x]+1;i<=bl[y]-1;i++) {
					su += sm[i];
				} 
				pt(su);
			}
		}
	}
	return 0;
}

 


莫队算法

也是分块算法的其中一种,可以用于处理一类离线的区间查询问题,适用范围广,复杂度O(n根号n)实际跑得飞快,
使用方法:分块之后,将问题排序,以左端点所在块为第一关键字,右端点为第二关键字。之后类似暴力的算法,暴力移动左右指针即可。
如果只有双指针,那么分块(根号n)
如果三指针(eg加上维度时间),分块(n^2/3)
四指针 n^(3/4),以此类推。

luogu1972 HH的项链

数据加强后代码过不了,,,反正只是记一个莫队的板子

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<cstdio>
#include<cmath>

using namespace std;
const int maxn = 500005;
int n,m;
struct node{
	int l,r,id;
}z[maxn];
int a[maxn],blo[maxn],ANS[maxn];
bool cmp(node x,node y) {
	if(blo[x.l]==blo[y.l]) return x.r < y.r;
	return x.l < y.l;
}
int tot[1000005];
int lzz=1,rzz,ans;
void ADD(int x) {
	if(!(tot[a[x]]++)) ans++; 
}
void DEL(int x) {
	if(!(--tot[a[x]])) ans--;
}
int main(){
    scanf("%d",&n);
	int fk = pow(n,0.5);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		blo[i] = blo[i-1];
		if(i%fk==1) blo[i]++;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++) {
		z[i].id = i;
		scanf("%d%d",&z[i].l,&z[i].r);
	}
	sort(z+1,z+1+m,cmp);
	for(int i=1;i<=m;i++) {
		while(rzz<z[i].r) ADD(++rzz);
		while(lzz>z[i].l) ADD(--lzz);
		while(rzz>z[i].r) DEL(rzz--);
		while(lzz<z[i].l) DEL(lzz++);
		ANS[z[i].id] = ans;
	}
	for(int i=1;i<=m;i++) {
		printf("%d\n",ANS[i]);
	}
	return 0;
}
 

 

bzoj2120 (hydro oj)

三阶莫队,也称带修莫队。
和上面hh的项链几乎一模一样,不同的一点点就是增加了time这个轴,修改时时间回退或者时间向前即可。

 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<cstdio>
#include<cmath>

using namespace std;
const int maxn = 20005;
struct node {
    int l,r,tm,id;
}z[maxn];

int cjp[maxn],cjcol[maxn],pacol[maxn],fk,blo[maxn];
bool cmp(node x,node y) {
	if(blo[x.l]!=blo[y.l]) return x.l < y.l;
	if(blo[x.r]!=blo[y.r]) return x.r < y.r;
	return x.tm > y.tm;
}
int a[maxn],ANS[maxn],ans;
int tot[1000005];
int n,m,ntim,qrm,lzz=1,rzz;
char ss[3];
void add(int x) {
	if(!(tot[a[x]])) ans++;
	tot[a[x]]++;
}
void del(int x) {
	tot[a[x]]--;
	if(!tot[a[x]]) ans--;
}
void mol(int p,int x) {
	if(lzz<=p&&p<=rzz) del(p); 
	a[p] = x;
	if(lzz<=p&&p<=rzz) add(p);
}
int main(){
//	freopen("2.in","r",stdin);
//	freopen("dp.out","w",stdout);
    scanf("%d%d",&n,&m);
	int fk = pow(n,0.66);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		blo[i] = blo[i-1];
		if(i%fk==1) blo[i]++;
	}
	for(int i=1;i<=m;i++) {
		scanf("%s",ss+1);
		if(ss[1]==‘Q‘) {
			++qrm;
			scanf("%d%d",&z[qrm].l,&z[qrm].r); z[qrm].id=qrm;
			z[qrm].tm = ntim;
		} else {
			++ntim; scanf("%d%d",&cjp[ntim],&cjcol[ntim]);
			pacol[ntim] = a[cjp[ntim]];
			a[cjp[ntim]] = cjcol[ntim];
		}
	}
	sort(z+1,z+1+qrm,cmp);
	for(int i=1;i<=qrm;i++) {
		while(rzz<z[i].r) add(++rzz);
		while(lzz>z[i].l) add(--lzz);
		while(rzz>z[i].r) del(rzz--);
		while(lzz<z[i].l) del(lzz++);
		while(ntim>z[i].tm) mol(cjp[ntim],pacol[ntim]),ntim--;
		while(ntim<z[i].tm) ntim++,mol(cjp[ntim],cjcol[ntim]);
		ANS[z[i].id] = ans;
	}
	for(int i=1;i<=qrm;i++) {
		printf("%d\n",ANS[i]);
	}
   	return 0;
}

 

OI康复计划

(0)
(0)
   
举报
评论 一句话评论(0
上一篇:获取命令帮助


下一篇:DAY5