莫队 – GNAQ 的心语屋

2018年3月14日2018年3月14日

BZOJ4241 历史研究

Mo’s Algorithm with Roll-Back

回滚莫队算法

对于删除操作难维护答案但添加易维护的或者添加难维护但是删除易维护的莫队题，可以使用回滚莫队算法。

历史研究是第一种

对于这种，我们选择

1.对于在同一个块内的询问， $O\left( \sqrt{n} \right)$ 暴力计算

2.对于不在同一块的询问，莫队排序后，形成了左端点在同一个块内的若干询问，

对于这些询问，我们只维护这个同块的下一个块的起点到这些询问的右端点的答案情况，因为右端点递增，左面固定在一处，所以只有添加。

然后回答每一个询问的时候暴力统计左端点到下一个块左端对答案的影响，统计完再改回去，

还有一个问题就是如果这个询问的左端点和上个的不在一个块，那直接重置答案统计变量和答案统计数组，暴力重新统计。

这样把复杂度压回了 $O\left( n\sqrt{n} \right)$ 的级别

下一点是添加难维护但是删除易维护的莫队题

对于这类我们采取和上面相同的思想，但是我没见过任何这样的题，属于有解法无题的东西。

对于同块询问当然还是暴力

非同块询问你需要这么做，莫队思想排序完后倒序处理。

对于左端点同块的若干询问，维护这个同块的起点到目前询问右端点的答案情况。倒序处理只有删除操作。

每次回答时暴力删除到询问的左端点，然后改回去。

对于目前询问和上一个询问左端点不同块的情况，做法和第一类问题一样。

最后是这个题的代码,全开longlong结果跑了大概20s……大概是ll太慢了。你可以少开几个ll

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;cmath&gt;
#include&lt;cstdlib&gt;
#include&lt;string&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
#include&lt;queue&gt;
#include&lt;vector&gt;
using namespace std;

struct asksx
{
	long long ans,l,r,codex;
}ask[100010]={0};

long long blksz,n,seq[100010]={0},q,nowans,belong[100010]={0};
long long setx[100010]={0},sta[100010]={0},sta2[100010]={0};

inline void readx(long long&amp; x)
{
	x=0; long long k=1; register char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline bool cmp1(asksx a,asksx b)
{
	if (belong[a.l]==belong[b.l]) return a.r&lt;b.r;
	else return a.l&lt;b.l;
}
inline bool cmp2(asksx a,asksx b) { return a.codex&lt;b.codex; }

inline void process1()
{
	int ent=n; blksz=sqrt(n);
	memcpy(setx,seq,sizeof(seq));
	sort(setx+1,setx+n+1);
	for (int i=1;i&lt;n;i++) if (setx[i]==setx[i+1]) { setx[i]=2*1e9; ent--; }
	sort(setx+1,setx+n+1);
	
	for (int i=1;i&lt;=n;i++)
	{
		int lx=1,rx=ent,mid;
		while (lx&lt;=rx)
		{
			mid=(lx+rx)&gt;&gt;1;
			if (setx[mid]==seq[i]) { seq[i]=mid; break; }
			else if (setx[mid]&gt;seq[i]) rx=mid-1;
			else lx=mid+1;
		}
	}
	
	for (int i=1;i&lt;=n;i++) belong[i]=(i-1)/blksz+1;
	sort(ask+1,ask+q+1,cmp1);
}

int main()
{
	readx(n); readx(q);
	for (int i=1;i&lt;=n;i++) readx(seq[i]);
	for (int i=1;i&lt;=q;i++)
	{
		readx(ask[i].l); readx(ask[i].r);
		ask[i].codex=i;
	}
	
	process1();
	
	long long lpos=1,rpos=0,qll=0,rawans;
	for (int i=1;i&lt;=q;i++)
	{
		if (belong[ask[i].l]!=belong[ask[i-1].l])
		{
			memset(sta,0,sizeof(sta));
			nowans=0; lpos=qll=belong[ask[i].l]*blksz+1; rpos=lpos-1;
		}
		if (belong[ask[i].l]==belong[ask[i].r])
		{
			long long cans=0;
			for (int j=ask[i].l;j&lt;=ask[i].r;j++)
			{
				sta2[seq[j]]++; cans=max(cans,sta2[seq[j]]*setx[seq[j]]);
			}
			for (int j=ask[i].l;j&lt;=ask[i].r;j++) sta2[seq[j]]=0;
			ask[i].ans=cans;
		}
		else
		{
			while (rpos&lt;ask[i].r)
			{
				rpos++; sta[seq[rpos]]++;
				nowans=max(nowans,sta[seq[rpos]]*setx[seq[rpos]]);
			}
			rawans=nowans;
			while (lpos&gt;ask[i].l)
			{
				lpos--; sta[seq[lpos]]++;
				rawans=max(rawans,sta[seq[lpos]]*setx[seq[lpos]]);
			}
			ask[i].ans=rawans;
			//roll_back
			while (lpos&lt;qll) { sta[seq[lpos]]--; lpos++; }
		}
	}
	
	sort(ask+1,ask+q+1,cmp2);
	for (int i=1;i&lt;=q;i++) printf("%lld\n",ask[i].ans);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<string>

#include<algorithm>

#include<iterator>

#include<queue>

#include<vector>

using namespace std;

struct asksx

{

long long ans,l,r,codex;

}ask[100010]={0};

long long blksz,n,seq[100010]={0},q,nowans,belong[100010]={0};

long long setx[100010]={0},sta[100010]={0},sta2[100010]={0};

inline void readx(long long& x)

{

x=0; long long k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline bool cmp1(asksx a,asksx b)

{

if (belong[a.l]==belong[b.l]) return a.r<b.r;

else return a.l<b.l;

}

inline bool cmp2(asksx a,asksx b) { return a.codex<b.codex; }

inline void process1()

{

int ent=n; blksz=sqrt(n);

memcpy(setx,seq,sizeof(seq));

sort(setx+1,setx+n+1);

for (int i=1;i<n;i++) if (setx[i]==setx[i+1]) { setx[i]=2*1e9; ent--; }

sort(setx+1,setx+n+1);

for (int i=1;i<=n;i++)

{

int lx=1,rx=ent,mid;

while (lx<=rx)

{

mid=(lx+rx)>>1;

if (setx[mid]==seq[i]) { seq[i]=mid; break; }

else if (setx[mid]>seq[i]) rx=mid-1;

else lx=mid+1;

}

for (int i=1;i<=n;i++) belong[i]=(i-1)/blksz+1;

sort(ask+1,ask+q+1,cmp1);

}

int main()

{

readx(n); readx(q);

for (int i=1;i<=n;i++) readx(seq[i]);

for (int i=1;i<=q;i++)

{

readx(ask[i].l); readx(ask[i].r);

ask[i].codex=i;

}

process1();

long long lpos=1,rpos=0,qll=0,rawans;

for (int i=1;i<=q;i++)

{

if (belong[ask[i].l]!=belong[ask[i-1].l])

{

memset(sta,0,sizeof(sta));

nowans=0; lpos=qll=belong[ask[i].l]*blksz+1; rpos=lpos-1;

}

if (belong[ask[i].l]==belong[ask[i].r])

{

long long cans=0;

for (int j=ask[i].l;j<=ask[i].r;j++)

{

sta2[seq[j]]++; cans=max(cans,sta2[seq[j]]*setx[seq[j]]);

}

for (int j=ask[i].l;j<=ask[i].r;j++) sta2[seq[j]]=0;

ask[i].ans=cans;

}

else

{

while (rpos<ask[i].r)

{

rpos++; sta[seq[rpos]]++;

nowans=max(nowans,sta[seq[rpos]]*setx[seq[rpos]]);

}

rawans=nowans;

while (lpos>ask[i].l)

{

lpos--; sta[seq[lpos]]++;

rawans=max(rawans,sta[seq[lpos]]*setx[seq[lpos]]);

}

ask[i].ans=rawans;

//roll_back

while (lpos<qll) { sta[seq[lpos]]--; lpos++; }

}

sort(ask+1,ask+q+1,cmp2);

for (int i=1;i<=q;i++) printf("%lld\n",ask[i].ans);

return 0;

}

2018年2月25日2018年2月25日

BZOJ3289 Mato的文件管理

Time Limit: 40 Sec (Total)

Memory Limit: 128 MB

莫队+树状数组维护

类(jiu)似(shi)冒泡排序的过程

注意优化时间

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;cstdlib&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
using namespace std;

int n,m,seq[100010]={0},fwt[100010]={0},setx[100010]={0},blksz=0,setlen=0;
struct asksx
{
	int codex,lx,rx,ans;
}ask[100010]={0};
int nowans=0;

inline void readx(int&amp; x)
{
	x=0; int k=1; register char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline int BinSearch(int val)
{
	int l=1,r=setlen,mid;
	while (1)
	{
		mid=(l+r)&gt;&gt;1;
		if (setx[mid]==val) return mid;
		else if (setx[mid]&gt;val) r=mid-1;
		else l=mid+1;
	}
}

inline void process1()
{
	setlen=n;
	memcpy(setx,seq,sizeof(seq));
	sort(setx+1,setx+n+1);
	for (int i=1;i&lt;=n;i++) if (setx[i]==setx[i+1]) { setx[i]=2*1e9; setlen--; }
	sort(setx+1,setx+n+1);
	for (int i=1;i&lt;=n;i++) seq[i]=BinSearch(seq[i]);
}

inline bool cmp1(asksx a,asksx b)
{
	if ((a.lx/blksz)==(b.lx/blksz)) return a.rx&lt;b.rx;
	else return a.lx&lt;b.lx;
}
inline bool cmp2(asksx a,asksx b) { return a.codex&lt;b.codex; }

inline void update(int pos,int val)
{
	while (pos&lt;=setlen)
	{
		fwt[pos]+=val;
		pos+=(pos&amp;(-pos));
	}
}

inline int query(int pos)
{
	int sum=0;
	while (pos)
	{
		sum+=fwt[pos];
		pos-=(pos&amp;(-pos));
	}
	return sum;
}

int main()
{
	readx(n); blksz=sqrt(n);
	for (int i=1;i&lt;=n;i++) readx(seq[i]);
	readx(m);
	for (int i=1;i&lt;=m;i++)
	{
		ask[i].codex=i;
		readx(ask[i].lx); readx(ask[i].rx);
	}
	process1();
	sort(ask+1,ask+m+1,cmp1); int lpos=1,rpos=0;
	for (int i=1;i&lt;=m;i++)
	{
		while (rpos&lt;ask[i].rx)
		{
			rpos++;
			update(seq[rpos],1); nowans+=(query(setlen)-query(seq[rpos]));
		}
		while (rpos&gt;ask[i].rx)
		{
			update(seq[rpos],-1); nowans-=(query(setlen)-query(seq[rpos]));
			rpos--;
		}
		while (lpos&lt;ask[i].lx)
		{
			update(seq[lpos],-1); nowans-=query(seq[lpos]-1);
			lpos++;
		}
		while (lpos&gt;ask[i].lx)
		{
			lpos--;
			update(seq[lpos],1); nowans+=query(seq[lpos]-1);
		}
		
		ask[i].ans=nowans;
	}
	
	sort(ask+1,ask+m+1,cmp2);
	for (int i=1;i&lt;=m;i++) printf("%d\n",ask[i].ans);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<iterator>

using namespace std;

int n,m,seq[100010]={0},fwt[100010]={0},setx[100010]={0},blksz=0,setlen=0;

struct asksx

{

int codex,lx,rx,ans;

}ask[100010]={0};

int nowans=0;

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline int BinSearch(int val)

{

int l=1,r=setlen,mid;

while (1)

{

mid=(l+r)>>1;

if (setx[mid]==val) return mid;

else if (setx[mid]>val) r=mid-1;

else l=mid+1;

}

inline void process1()

{

setlen=n;

memcpy(setx,seq,sizeof(seq));

sort(setx+1,setx+n+1);

for (int i=1;i<=n;i++) if (setx[i]==setx[i+1]) { setx[i]=2*1e9; setlen--; }

sort(setx+1,setx+n+1);

for (int i=1;i<=n;i++) seq[i]=BinSearch(seq[i]);

}

inline bool cmp1(asksx a,asksx b)

{

if ((a.lx/blksz)==(b.lx/blksz)) return a.rx<b.rx;

else return a.lx<b.lx;

}

inline bool cmp2(asksx a,asksx b) { return a.codex<b.codex; }

inline void update(int pos,int val)

{

while (pos<=setlen)

{

fwt[pos]+=val;

pos+=(pos&(-pos));

}

inline int query(int pos)

{

int sum=0;

while (pos)

{

sum+=fwt[pos];

pos-=(pos&(-pos));

}

return sum;

}

int main()

{

readx(n); blksz=sqrt(n);

for (int i=1;i<=n;i++) readx(seq[i]);

readx(m);

for (int i=1;i<=m;i++)

{

ask[i].codex=i;

readx(ask[i].lx); readx(ask[i].rx);

}

process1();

sort(ask+1,ask+m+1,cmp1); int lpos=1,rpos=0;

for (int i=1;i<=m;i++)

{

while (rpos<ask[i].rx)

{

rpos++;

update(seq[rpos],1); nowans+=(query(setlen)-query(seq[rpos]));

}

while (rpos>ask[i].rx)

{

update(seq[rpos],-1); nowans-=(query(setlen)-query(seq[rpos]));

rpos--;

}

while (lpos<ask[i].lx)

{

update(seq[lpos],-1); nowans-=query(seq[lpos]-1);

lpos++;

}

while (lpos>ask[i].lx)

{

lpos--;

update(seq[lpos],1); nowans+=query(seq[lpos]-1);

}

ask[i].ans=nowans;

}

sort(ask+1,ask+m+1,cmp2);

for (int i=1;i<=m;i++) printf("%d\n",ask[i].ans);

return 0;

}

2018年2月23日2018年2月23日

带修莫队板子

丢板子还需要别的内容吗

题目参见数颜色

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;cstdlib&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
using namespace std;

struct asksx
{
    int leftx,rightx,mod_time;
    int ansx,codex;
}ask[10010]={0};
struct modifies
{
    int pos,val;
}modi[10010]={0};
int n,m,seq[10010]={0},modtime=0,blksz=0;
int ctr1=0,ctr2=0,lpos=0,rpos=0,anss=0;
char ch=0;
int exi[1000010]={0},belong[10010]={0};

inline void readx(int&amp; x)
{
    x=0; int k=1; register char ch=0;
    while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

inline bool cmp1(asksx a,asksx b)
{
    if (belong[a.leftx]==belong[b.leftx])
    {
        if (belong[a.rightx]==belong[b.rightx]) return a.mod_time&lt;b.mod_time;
        return belong[a.rightx]&lt;belong[b.rightx];
    }
    return belong[a.leftx]&lt;belong[b.leftx];
}
inline bool cmp2(asksx a,asksx b) { return a.codex&lt;b.codex; }

inline void process1(int i)
{
    if (modi[modtime].pos&gt;=lpos &amp;&amp; modi[modtime].pos&lt;=rpos)
    {
        exi[seq[modi[modtime].pos]]--;
        exi[modi[modtime].val]++;
        if (exi[seq[modi[modtime].pos]]==0) anss--;
        if (exi[modi[modtime].val]==1) anss++;
    }
}

int main()
{
    readx(n); readx(m); blksz=sqrt(n);
    for (int i=1;i&lt;=n;i++) belong[i]=(i/blksz)+1;
    for (int i=1;i&lt;=n;i++) readx(seq[i]);
    for (int i=1;i&lt;=m;i++)
    {
        ch=0; while (ch&lt;'A' || ch&gt;'Z') ch=getchar();
        if (ch=='Q')
        {
            ctr1++; readx(ask[ctr1].leftx); readx(ask[ctr1].rightx);
            ask[ctr1].mod_time=modtime; ask[ctr1].codex=ctr1;
        }
        else
        {
            modtime++; ctr2++;
            readx(modi[ctr2].pos); readx(modi[ctr2].val);
        }
    }
    
    modtime=0; sort(ask+1,ask+ctr1+1,cmp1); lpos=rpos=0;
    for (int i=1;i&lt;=ctr1;i++)
    {
        while (ask[i].mod_time&gt;modtime)
        {
            modtime++;
            process1(i); swap(seq[modi[modtime].pos],modi[modtime].val);
        }
        while (ask[i].mod_time&lt;modtime)
        {
            process1(i); swap(seq[modi[modtime].pos],modi[modtime].val);
            modtime--;
        }
        while (rpos&gt;ask[i].rightx)
        {
            exi[seq[rpos]]--; if (exi[seq[rpos]]==0) anss--;
            rpos--;
        }
        while (rpos&lt;ask[i].rightx)
        {
            rpos++;
            exi[seq[rpos]]++; if (exi[seq[rpos]]==1) anss++;
        }
        while (lpos&lt;ask[i].leftx)
        {
            exi[seq[lpos]]--; if (exi[seq[lpos]]==0) anss--;
            lpos++;
        }
        while (lpos&gt;ask[i].leftx)
        {
            lpos--;
            exi[seq[lpos]]++; if (exi[seq[lpos]]==1) anss++;
        }
        ask[i].ansx=anss;
    }
    
    sort(ask+1,ask+ctr1+1,cmp2);
    for (int i=1;i&lt;=ctr1;i++) printf("%d\n",ask[i].ansx);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<iterator>

using namespace std;

struct asksx

{

int leftx,rightx,mod_time;

int ansx,codex;

}ask[10010]={0};

struct modifies

{

int pos,val;

}modi[10010]={0};

int n,m,seq[10010]={0},modtime=0,blksz=0;

int ctr1=0,ctr2=0,lpos=0,rpos=0,anss=0;

char ch=0;

int exi[1000010]={0},belong[10010]={0};

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline bool cmp1(asksx a,asksx b)

{

if (belong[a.leftx]==belong[b.leftx])

{

if (belong[a.rightx]==belong[b.rightx]) return a.mod_time<b.mod_time;

return belong[a.rightx]<belong[b.rightx];

}

return belong[a.leftx]<belong[b.leftx];

}

inline bool cmp2(asksx a,asksx b) { return a.codex<b.codex; }

inline void process1(int i)

{

if (modi[modtime].pos>=lpos && modi[modtime].pos<=rpos)

{

exi[seq[modi[modtime].pos]]--;

exi[modi[modtime].val]++;

if (exi[seq[modi[modtime].pos]]==0) anss--;

if (exi[modi[modtime].val]==1) anss++;

}

int main()

{

readx(n); readx(m); blksz=sqrt(n);

for (int i=1;i<=n;i++) belong[i]=(i/blksz)+1;

for (int i=1;i<=n;i++) readx(seq[i]);

for (int i=1;i<=m;i++)

{

ch=0; while (ch<'A' || ch>'Z') ch=getchar();

if (ch=='Q')

{

ctr1++; readx(ask[ctr1].leftx); readx(ask[ctr1].rightx);

ask[ctr1].mod_time=modtime; ask[ctr1].codex=ctr1;

}

else

{

modtime++; ctr2++;

readx(modi[ctr2].pos); readx(modi[ctr2].val);

}

modtime=0; sort(ask+1,ask+ctr1+1,cmp1); lpos=rpos=0;

for (int i=1;i<=ctr1;i++)

{

while (ask[i].mod_time>modtime)

{

modtime++;

process1(i); swap(seq[modi[modtime].pos],modi[modtime].val);

}

while (ask[i].mod_time<modtime)

{

process1(i); swap(seq[modi[modtime].pos],modi[modtime].val);

modtime--;

}

while (rpos>ask[i].rightx)

{

exi[seq[rpos]]--; if (exi[seq[rpos]]==0) anss--;

rpos--;

}

while (rpos<ask[i].rightx)

{

rpos++;

exi[seq[rpos]]++; if (exi[seq[rpos]]==1) anss++;

}

while (lpos<ask[i].leftx)

{

exi[seq[lpos]]--; if (exi[seq[lpos]]==0) anss--;

lpos++;

}

while (lpos>ask[i].leftx)

{

lpos--;

exi[seq[lpos]]++; if (exi[seq[lpos]]==1) anss++;

}

ask[i].ansx=anss;

}

sort(ask+1,ask+ctr1+1,cmp2);

for (int i=1;i<=ctr1;i++) printf("%d\n",ask[i].ansx);

return 0;

}