好久好久没有碰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;
}
踩
(0)
赞
(0)
举报
评论 一句话评论（0）