[莫队算法] - cool's Blog
[莫队算法]
最近又看了一下莫队，发现我以前完全理解错了莫队算法。
莫队算法适用于无修（带修不会啊QAQ@lbn187）的区间询问且若已知[L,R]的答案能够以较快的速度求出[L-1,R],[L+1,R],[L,R-1],[L,R+1],那么就可以使用莫队。
莫队是将所有区间按照一定顺序排序，使得这个区间移动次数较少。
最优的方法就是曼哈顿距离的最小生成树。但写起来太麻烦。
用这种方法排序是比较优秀的：如果L1/blk=L2/blk，那么就按R排序，否则按L排序。
经典例题小Z的袜子（叫你每天代码抄抄）
[51nod1290]询问区间内多少对数差的绝对值<=k，k为全局给定。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define N 50010
#define M 150010
#define ll long long
using namespace std;
struct zhl
{
int l,r,id;
zhl(){}
zhl(int L,int R,int ID):l(L), r(R), id(ID){}
}eg[N];
int l,r,n,k,q,pos[N],blk,len,gg[M],a[N],b[N],c[N],x,y;
ll Ans,ans[N];
int cmp(zhl x,zhl y)
{
return pos[x.l]^pos[y.l]?x.l < y.l:x.r < y.r;
}
int g[M];
void update(int x,int y)
{
for (;x <= len;x += x&-x)
g[x] += y;
}
int query(int x)
{
int y = 0;
for (;x;x -= x&-x)
y += g[x];
return y;
}
void solve()
{
l = r = 1, Ans = 0;
update(a[1],1);
rep(i,1,q)
{
int L = eg[i].l,R = eg[i].r;
for (;l < L;l++) update(a[l],-1),Ans -= query(c[l])-query(b[l]-1);
for (;l > L;update(a[l],1)) l--,Ans += query(c[l])-query(b[l]-1);
for (;r < R;update(a[r],1)) r++,Ans += query(c[r])-query(b[r]-1);
for (;r > R;r--) update(a[r],-1),Ans -= query(c[r])-query(b[r]-1);
ans[eg[i].id] = Ans;
}
}
int main()
{
scanf("%d%d%d",&n,&k,&q); blk = sqrt(n);
rep(i,1,n)
{
scanf("%d",&a[i]);
gg[++len] = a[i];
gg[++len] = a[i]+k;
gg[++len] = a[i]-k;
}
sort(gg+1,gg+len+1);
len = unique(gg+1,gg+len+1)-gg-1;
rep(i,1,n)
{
b[i] = lower_bound(gg+1,gg+len+1,a[i]-k)-gg;
c[i] = lower_bound(gg+1,gg+len+1,a[i]+k)-gg;
a[i] = lower_bound(gg+1,gg+len+1,a[i])-gg;
pos[i] = (i-1)/blk;
}
rep(i,1,q)
{
scanf("%d%d",&x,&y);
eg[i] = zhl(x+1,y+1,i);
}
sort(eg+1,eg+q+1,cmp);
solve();
rep(i,1,q) printf("%lld\n",ans[i]);
return 0;
}
[bzoj4540]求一段区间的所有子区间的最小值的和。
考虑加入一个数的贡献，令p为[L,R]的最小值。
那么（p-L+1）*a[p]是其中一部分的贡献，还有的贡献在[p+1,R]。
令sl[i]为1~i的答案，那么sl[R]-sl[p]就是[p+1,R]的答案。
为什么呢？因为p是最小值，也就是说[p+1,R]的所有值的sl都是以sl[p]为基础转移的。
还有一点，莫队的时候应该先增加区间，再减小区间，不然有可能会有L>R的情况，会biubiu。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 100010
int L[N],R[N],stk[N],pos[N],pw[20],n,q,top,blk,Left,Right;
ll sl[N],sr[N],a[N],ans[N],now;
int lg[N],f[N][20];
struct xfy
{
int l,r,id;
}eg[N];
void checkmin(int& x,int y)
{
if (a[x] > a[y]) x = y;
}
int getmin(int x,int y)
{
if (x > y) Swap(x,y);
int l = lg[y-x+1],r1 = f[x][l],r2 = f[y-pw[l]+1][l];
return a[r1]<a[r2]?r1:r2;
}
void updatel(int l,int r,int ty)
{
int o = getmin(l,r);
ll res = a[o]*(r-o+1)+sr[l]-sr[o];
now += res*ty;
}
void updater(int l,int r,int ty)
{
int o = getmin(l,r);
ll res = a[o]*(o-l+1)+sl[r]-sl[o];
now += res*ty;
}
int cmp(xfy x,xfy y)
{
return pos[x.l] == pos[y.l]?x.r<y.r:x.l<y.l;
}
int main()
{
scanf("%d%d",&n,&q); blk = sqrt(n);
pw[0] = 1;
rep(i,1,18) pw[i] = pw[i-1]+pw[i-1];
rep(i,1,n) scanf("%lld",&a[i]);
rep(i,1,n)
{
for (;top&&a[stk[top]]>=a[i];R[stk[top--]]=i);
stk[++top] = i;
}
for (;top;R[stk[top--]]=n+1);
drep(i,n,1)
{
for (;top&&a[stk[top]]>a[i];L[stk[top--]]=i);
stk[++top] = i;
}
for (;top;L[stk[top--]]=0);
rep(i,1,n) sl[i] = sl[L[i]]+a[i]*(i-L[i]);
drep(i,n,1) sr[i] = sr[R[i]]+a[i]*(R[i]-i);
lg[0] = -1;
rep(i,1,n) lg[i] = lg[i>>1]+1,pos[i] = (i-1)/blk,f[i][0] = i;
rep(j,1,18)
{
rep(i,1,n)
{
f[i][j] = f[i][j-1];
if (i+pw[j-1] <= n) checkmin(f[i][j],f[i+pw[j-1]][j-1]);
}
}
rep(i,1,q) scanf("%d%d",&eg[i].l,&eg[i].r),eg[i].id = i;
sort(eg+1,eg+q+1,cmp);
Left = Right = 1;now = a[1];
rep(i,1,q)
{
int l = eg[i].l,r = eg[i].r;
for (;Right < r;Right++) updater(Left,Right+1,1);
for (;Left > l;Left--) updatel(Left-1,Right,1);
for (;Right > r;Right--) updater(Left,Right,-1);
for (;Left < l;Left++) updatel(Left,Right,-1);
ans[eg[i].id] = now;
}
rep(i,1,q) printf("%lld\n",ans[i]);
return 0;
}
2022年8月07日 15:10
The HPSEB Bill Payment, new connection and other grievances taken up through an online portal. There are various other sources, through which the payment of HPSEB electricity bill processed to ensure customers provide better opportunities. The payment gateway of electricity bills online makes it easy for consumers to ensure they don’t miss the due date and timely make payment of their dues to enjoy unbreakable electricity service. HPSEB online bill payment Himachal Pradesh State Electricity Board does undertake the electricity supply to the customer in the state. It is a state-owned department which is fully under control of the state electricity board and provides various services of electricity to every domestic and commercial purpose.
2025年3月07日 18:07
Nice post. I discover some thing much harder on various blogs everyday. Most commonly it is stimulating to read content off their writers and rehearse something at their store. I’d opt to use some using the content in my small weblog no matter whether you don’t mind. Natually I’ll offer you a link with your internet weblog. Thank you sharing. Binary Signals
2025年3月11日 15:44
Real informative and fantastic anatomical structure of subject material , now that’s user pleasant . http://www.5starsstocks.com/
2025年3月16日 00:18
There are incredibly plenty of details like that take into consideration. That is the fantastic specify raise up. I offer the thoughts above as general inspiration but clearly you can find questions such as the one you raise up where the most critical factor will probably be doing work in honest very good faith. I don?t know if guidelines have emerged about things like that, but More than likely that your particular job is clearly identified as a fair game. Both boys and girls notice the impact of a moment’s pleasure, for the rest of their lives. Binary Options
2025年3月21日 23:42
You should get involved in a contest for example of the most useful blogs on-line. Let me recommend this page! heads or tails
2025年3月24日 22:17
Hello! I just now wish to provide a huge thumbs up for the great information you could have here during this post. We are coming back to your website for further soon. 바카라 사이트
2025年3月28日 14:24
Thank you for your own hard work on this website. Ellie enjoys conducting investigation and it is obvious why. All of us learn all of the compelling mode you produce simple tricks through this blog and as well cause participation from other ones about this area of interest then our daughter is now starting to learn a lot of things. Take advantage of the rest of the new year. You have been conducting a very good job. binary options signals
2025年3月31日 20:08
My brother suggested I could like this weblog. He was totally suitable. This publish truly created my day. You cann’t imagine merely how much time I had spent for this info! Thanks! crypto bot
2025年4月20日 23:57
Thank you so much for giving my family an update on this issue on your web-site. Please realise that if a brand new post appears or if perhaps any adjustments occur to the current post, I would be interested in reading a lot more and focusing on how to make good use of those strategies you reveal. Thanks for your efforts and consideration of other people by making this web site available. افلام مترجمة
2025年4月25日 03:03
Aw, this was a very nice post. In concept I wish to put in writing like this moreover ?taking time and precise effort to make an excellent article?but what can I say?I procrastinate alot and certainly not appear to get one thing done. mobile trading platform
2025年5月26日 15:51
As I website owner I believe the articles here is really fantastic , thankyou for your efforts. binary options trading
2025年6月05日 01:02
You completed several nice points there. I did a search on the subject and found a good number of persons will consent with your blog. binary trading signals
2025年6月13日 23:57
we may always need to do some credit specially if we weant to invest on something” verhuisfirma antwerpen
========================
It is an extremely amazing powerful resource that you’re offering and you just provide it away cost-free!! I comparable to discovering websites ones comprehend the particular valuation on supplying you with a excellent learning resource for zero cost. We truly dearly loved examining this web site. Regards! YouTube MP3
===========================
I have seen similar about this expression. But it seems your’s is different and best. filmyzilla
2025年6月17日 21:09
It was a real pleasure getting to your site a short while ago. I came here this day hoping to find out something new. And I was not upset. Your ideas about new solutions on this subject were helpful and a good help to me. Thank you for making time to write out these things as well as sharing your thinking. Paul Feller
============================
I was just having a conversation over this I am glad I came across this it cleared some of the questions I had. binary option bots
2025年7月04日 02:15
Can I just now say such a relief to uncover a person that actually knows what theyre preaching about over the internet. You actually have learned to bring a worry to light and produce it important. More people need to look at this and can see this side with the story. I cant think youre less popular simply because you definitely provide the gift. trading system
2025年7月09日 17:28
Hi. Thank you for making this site . I m working on betting online niche and have found this site using search on bing . Will be sure to look more of your content.CLICK HERE best ranked private servers