基础莫队

yesterday once more !

有空记得认真写一下啊 :)

参考资料

http://keyblog.cn/article-148.html

https://blog.csdn.net/TDD_Master/article/details/90611940

https://www.cnblogs.com/caijiaming/p/10896352.html

https://www.cnblogs.com/WAMonster/p/10118934.html

莫队算法

题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=6534

// 33771721	2020-08-16 23:36:23	Accepted	6534	483MS	3132K	1947 B	G++	mainland

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


const int maxv=3e5;
const int maxv3=3*maxv;

int c[maxv3];


int maxVal;
inline int lowbit(int x){ return x&-x;}
void update(int p,int v){
	for(;p<=maxVal;p+=lowbit(p))
		c[p]+=v;
}
int sum(int p){
	int s=0; for(;p;p-=lowbit(p)) s+=c[p];
	return s;
}

int belong[maxv];

struct query{
	int l,r,id;
	bool operator<(const query &rhs) const{
		if(belong[l]==belong[rhs.l]) return belong[r]<belong[rhs.r];
		return belong[l]<belong[rhs.l];
	}
}q[maxv];

int n,m,k;
int a[maxv];
int b[maxv3];
int l[maxv];
int r[maxv];
int w[maxv];

ll ans[maxv];

ll res=0;


void add(int x){

	//cout<<l[x]-1<<endl;

	res+=sum(r[x])-sum(l[x]-1);
	update(w[x],1);
}
void del(int x){
	
//	cout<<l[x]-1<<endl;

	update(w[x],-1);
	res-=sum(r[x])-sum(l[x]-1);
}

int main(){
	while(~scanf("%d%d%d",&n,&m,&k)){
		int tot=1;
		int block= sqrt(n);
		inc(i,1,n){
		   	scanf("%d",a+i);
			
			b[tot++]=a[i];
			b[tot++]=a[i]-k;
			b[tot++]=a[i]+k;

			belong[i]=i/block;
		}

		sort(b+1,b+tot);

		maxVal=tot;
		inc(i,1,n){
			l[i]=lower_bound(b+1,b+tot,a[i]-k)-b;
			r[i]=lower_bound(b+1,b+tot,a[i]+k)-b;
			w[i]=lower_bound(b+1,b+tot,a[i])-b;
		}

		inc(i,1,m){
			scanf("%d%d",&q[i].l,&q[i].r);
			q[i].id=i;
		}

		sort(q+1,q+m+1);
		int l=1,r=0;
		res=0;
		inc(i,1,m){
			while(l<q[i].l) del(l++);
			while(l>q[i].l) add(--l);
			while(r<q[i].r) add(++r);
			while(r>q[i].r) del(r--);
			ans[q[i].id]=res;
		}
		inc(i,1,m) printf("%d\n",ans[i]);
	}
	return 0;
}

带修莫队

//https://blog.csdn.net/qq_34493840/article/details/94031793 
#include <bits/stdc++.h> 
using namespace std; 
//修改了这一行就对了
//之前的数组开小了
//const int maxn = 5e4 + 100; 
const int maxn = 5e5 + 100; 
const int maxm = 1e6 + 100; 

template <typename T> 
inline void read(T &s) {
	s = 0; 
	T w = 1, ch = getchar(); 
	while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
	while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
	s *= w; 
}

int n, m, csize, qsize, ans; 
int a[maxn], res[maxn], pos[maxn], cnt[maxm];  
struct change { int p, col; } c[maxn]; // 记录修改的数组
struct query { int l, r, t, id; } q[maxn]; // 记录查询的数组

inline bool cmp(query aa, query bb) { 
	return pos[aa.l] == pos[bb.l] ? (pos[aa.r] == pos[bb.r] ? aa.t < bb.t : aa.r < bb.r) : aa.l < bb.l;
}
inline void del(int x) { if (--cnt[x] == 0) --ans;  }
inline void add(int x) { if (++cnt[x] == 1) ++ans;  }

int main() {
//	freopen("1.in", "r", stdin); 
//	freopen("1.out", "w", stdout); 
	read(n), read(m); 
	int blo = pow(n, 0.666666); // n的2/3次方
	for (int i = 1; i <= n; ++i) {
		read(a[i]); 
		pos[i] = i / blo; 
	}
	char opt[10]; 
	for (int i = 1; i <= m; ++i) {
		scanf("%s", opt); 
		if (opt[0] == 'Q') {
			++qsize; 
			read(q[qsize].l), read(q[qsize].r); 
			q[qsize].t = csize; 
			q[qsize].id = qsize; 
		}
		else {
			++csize; 
			read(c[csize].p), read(c[csize].col); 
		}
	}
	sort(q + 1, q + qsize + 1, cmp); 
	int l = 1, r = 0, t = 0; 
	for (int i = 1; i <= qsize; ++i) {
		int ql = q[i].l, qr = q[i].r; 
		while (t < q[i].t) {
			++t;
			if (l <= c[t].p && r >= c[t].p) {
				del(a[c[t].p]); 
				add(c[t].col); 
			}
			swap(a[c[t].p], c[t].col); 
		}
		while (t > q[i].t) {
			if (l <= c[t].p && r >= c[t].p) {
				del(a[c[t].p]); 
				add(c[t].col); 
			}
			swap(a[c[t].p], c[t].col);
			--t;
		}

		while (l < ql) del(a[l++]); 
		while (l > ql) add(a[--l]); 
		while (r < qr) add(a[++r]); 
		while (r > qr) del(a[r--]); 
		res[q[i].id] = ans; 
	}
	for (int i = 1; i <= qsize; ++i) 
		printf("%d\n", res[i]); 
	return 0; 
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!