Pluto_Rabbit's Blog

蒟蒻妹纸一枚,轻拍

【学习】莫队算法

Jacinth posted @ 2016年2月16日 20:46 in Lerning with tags 学习 莫队算法 Learning , 787 阅读

感觉是个炒鸡高级的算法。。。由于本人太渣了。。。只做了2题QAQ

%%%lbn187 _(:зゝ∠)_

lbn上课讲了CDQ分治,莫队,还有各种奇奇怪怪的离线问题

感觉莫队和分块好像啊。。。

我之前做过一道(捂脸)分块的题目哎。。。

BZOJ-2957

(我猜泥萌肯定没想到竟然有人拿之前的程序来充数。。。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#define I int
#define D double
#define NN 100005
#define NNN 330
using namespace std;

struct REC
{
	int l;
	D num[NNN];
	void add(D xx)	{num[++l]=xx;}
	int finds(D xx)
	{
		int left=1,right=l,tmp=0;
		while (left<=right)
		{
			int mid=(left+right)>>1;
			if (num[mid]>xx) tmp=mid,right=mid-1; else left=mid+1;
		}
		return tmp;
	}
};
REC q[NN];
int n,m,x,y,len,cnt,now,ans,lenn[NN];
D w[NN],maxx;

int main()
{
	scanf("%d%d",&n,&m);
	len=(I)sqrt((D)n);
	while (len*len>n) len--;
	cnt=n/len+(n%len==0?0:1);
	for (int i=1;i<cnt;++i) lenn[i]=len;
	lenn[cnt]=n-(cnt-1)*len;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		w[x]=(D)y/(D)x;
		now=(x-1)/len+1;
		maxx=0; q[now].l=0;
		for (int j=len*(now-1)+1;j<=len*(now-1)+lenn[now];++j)
		if (w[j]>maxx)
			q[now].add(w[j]),maxx=w[j];
		ans=q[1].l;
		maxx=q[1].num[ans];
		for (int j=2;j<=cnt;++j)
		if (q[j].num[q[j].l]>maxx)
		{
			ans+=q[j].l-q[j].finds(maxx)+1;
			maxx=q[j].num[q[j].l];
		}
		printf("%d\n",ans);
	}
	return 0;
}

要不先看看莫队的题。。。

BZOJ-2038

听说比较像是模板题所以就先下刀了QAQ。。。调了好久发现第一个sort的位置放到了求p数组的前面,然后就愉快GG了

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#define NN 50010
#define LL long long
using namespace std;

struct REC
{
	int l,r,num;
	LL x,y;
}a[NN];
int c[NN],p[NN],block,n,m;
LL s[NN],ans=0;
bool cmp1(REC xx,REC yy)
{	if (p[xx.l]==p[yy.l]) return xx.r<yy.r;	else return xx.l<yy.l;}
LL GCD(LL xx,LL yy)
{
	while (xx) xx^=yy^=xx^=yy%=xx;
	return yy;
}
bool cmp2(REC xx,REC yy) {return xx.num<yy.num;}
LL sqr(LL xx) { return xx*xx;}
void update(int xx,int yy)
{
	ans-=sqr(s[c[xx]]);
	s[c[xx]]+=yy;
	ans+=sqr(s[c[xx]]);
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf("%d",&c[i]);
	for (int i=1;i<=m;++i) scanf("%d%d",&a[i].l,&a[i].r),a[i].num=i;
	block=int(sqrt(n));
	for (int i=1;i<=n;++i) p[i]=(i-1)/block+1;
	sort(a+1,a+1+m,cmp1);
	for (int i=1,l=1,r=0;i<=m;++i)
	{
		for (;r<a[i].r;++r) update(r+1,1);
		for (;r>a[i].r;--r) update(r,-1);
		for (;l<a[i].l;++l) update(l,-1);
		for (;l>a[i].l;--l) update(l-1,1);
		if (a[i].l==a[i].r) { a[i].x=0ll,a[i].y=1ll; continue;}
		a[i].x=ans-(a[i].r-a[i].l+1),a[i].y=(LL)(a[i].r-a[i].l+1)*(a[i].r-a[i].l);
		LL tmp=GCD(a[i].x,a[i].y);
		a[i].x/=tmp,a[i].y/=tmp;
	}
	sort(a+1,a+1+m,cmp2);
	for (int i=1;i<=m;++i) printf("%lld/%lld\n",a[i].x,a[i].y);
	return 0;
}

BZOJ-1878

突然发现怎么边上的人都在艹这道题。。。第一眼看过去好像莫队啊(中毒。。。)题解告诉我这是树状数组?然后再差点弃疗的时候。。。窝还是写了这道题

其实把上面的GCD求最简分数的地方去掉。。。再把update里面的东东改一改。。。就1A辣O(∩_∩)O~~

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#define NN 50010
#define MM 200010
#define CC 1000010
#define LL long long
using namespace std;

struct REC
{
	int l,r,x,num;
}a[MM];
int c[NN],s[CC],ans,p[NN],n,m,block;
void update(int xx,int yy)
{
	if (s[c[xx]]) ans--;
	s[c[xx]]+=yy;
	if (s[c[xx]]) ans++;
}
bool cmp1(REC xx,REC yy)
{	if (p[xx.l]==p[yy.l]) return xx.r<yy.r; else return xx.l<yy.l;}
bool cmp2(REC xx,REC yy)	{return xx.num<yy.num;}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&c[i]);
	scanf("%d",&m);
	for (int i=1;i<=m;++i) scanf("%d%d",&a[i].l,&a[i].r),a[i].num=i;
	block=int(sqrt(n));
	for (int i=1;i<=n;++i) p[i]=(i-1)/block+1;
	sort(a+1,a+1+m,cmp1);
	for (int i=1,l=1,r=0;i<=m;++i)
	{
		for (;r<a[i].r;r++) update(r+1,1);
		for (;r>a[i].r;r--) update(r,-1);
		for (;l<a[i].l;l++) update(l,-1);
		for (;l>a[i].l;l--) update(l-1,1);
		a[i].x=ans;
	}
	sort(a+1,a+1+m,cmp2);
	for (int i=1;i<=m;++i) printf("%d\n",a[i].x);
	return 0;
}

所以本人好渣啊。。。。

【特长(zhǎng)生来了,本宝宝就被塔萌碾压惹

Avatar_small
AP 10th Telugu Quest 说:
2022年9月14日 22:20

We advised contacting your Telugu teacher to get a chapter-wise practice model question paper for both levels of exams held under the school or board level and follow the link to download All AP SSC 10th Class Telugu Model Question Papers 2023 with Solutions. Every student everyone can download AP 10th Telugu Model Paper 2023 chapter-wise for paper-1, paper-2 exam theory, objective, AP 10th Telugu Question Paper multiple-choice questions (MCQ), Bit Question Bank with practice study material with IMP Question paper pdf with old scheme suggestions for AP 10th Class students 2023 to the Telugu Subject.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter