标签：little   code   https   立方和   lan   void   memset   uniq   ++i   

莫队算法~练习一

gym卡了莫队，于是趁这个机会学一下莫队

莫队的核心是分块排序，这种特殊的排序方法将任务按排序后的顺序完成，可以在解决绝大多数无修改的离线区间问题中极大的优化时间（优化了$\sqrt n$左右）。

Sona

NBUT - 1457

题意：n个数，寻问10000次，任意区间内的相等数的次数的立方和。

题解：将n个数离散化后，用莫队将询问分块排序，暴力计算出答案，在按原顺序输出结果。

#include
#include
#include
#include
#include
#define ll long long
using namespace std;

ll n,a[100007],t,head,maze,size,ak[100007],num[100007],ans[100007],b[100007];
struct madoka{
	ll l;
	ll r;
	ll p;
}ma[100007];
long long int qpow(long long int x,long long int n)
{
    long long int res=1;
	while(n>0)
	{
	   if(n%2==1)	
	   {
	   	 res=res*x;
	   	 res=res;
	   }
	   x=x*x;
	   x=x;
	   n>>=1;
	}
	return res;	
}
bool cmp(madoka a1,madoka a2){
	if(ak[a1.l]==ak[a2.l]){
		return a1.rma[i].l){
			l--;
			ansn-=qpow(num[a[l]],3);
			num[a[l]]++;
			ansn+=qpow(num[a[l]],3);
		}
		while(r>ma[i].r){
			ansn-=qpow(num[a[r]],3);
			num[a[r]]--;
			ansn+=qpow(num[a[r]],3);
			r--;
		}
		while(l

Little Elephant and Array

CodeForces - 220B

题意：n个数，寻问10000次，任意区间内的相等数的次数与其数相等的个数。

题解：与上题差不多，但有个坑要注意下，离散化后会导致值改变，所以某数的次数要与它离散化前比较，之后便是莫队板子。

#include
#include
#include
using namespace std;

int n,m,t,a[100007],b[100007],num[100007],size,maze,head,ak[100007],ans[100007];

struct madoka{
	int l;
	int r;
	int p;
}ma[100007];

bool cmp(madoka a1,madoka a2){
	if(ak[a1.l]==ak[a2.l]){
		return a1.rma[i].r){
			if(num[a[r]]==b[a[r]]){
				ansn--;
			}
			num[a[r]]--;
			if(num[a[r]]==b[a[r]]){
				ansn++;
			}
			r--;
		}
		while(l>ma[i].l){
			l--;
			if(num[a[l]]==b[a[l]]){
				ansn--;
			}
			num[a[l]]++;
			if(num[a[l]]==b[a[l]]){
				ansn++;
			}
		}
		while(l

莫队算法~练习一

标签：little   code   https   立方和   lan   void   memset   uniq   ++i   

原文地址：https://www.cnblogs.com/whitelily/p/13194854.html