〇、前言 ¶
我曾一度认为暴力就是一个垃圾东西而不想打，直到现在我才知道，原来我根本打不来暴力......
壹、序列分块 ¶
这种题型一般都会给你一个序列的东西，可能有修改可能没有，让你维护一些并不是很好使用 \(\log\) 的方法维护的信息，比如区间的区间和等等，这个时候就要使用较为暴力的分块做法了。
◆ [POJ3264]Balanced Lineup
区间极差，本来可以使用 \(\log\) 的数据结构，但是分块也是很好的。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
// #define NDEBUG
#include<cassert>
namespace Elaina{
#define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
#define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
#define mmset(a, b) memset(a, b, sizeof a)
// #define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T>inline T fab(T x){ return x<0? -x: x; }
template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
template<class T>inline T readin(T x){
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template<class T>inline void writc(T x, char s='\n'){
static int fwri_sta[1005], fwri_ed=0;
if(x<0) putchar('-'), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
}
using namespace Elaina;
const int maxn=50000;
const int celia=230;
inline int getblo(int x){ return (x-1)/celia+1; }
inline int getl(int id){ return (id-1)*celia+1; }
inline int getr(int id){ return id*celia; }
int a[maxn+5], n, q;
int minn[celia+5], maxx[celia+5];
inline void input(){
n=readin(1), q=readin(1);
rep(i, 1, n) a[i]=readin(1);
}
inline void buildBlock(){
rep(i, 1, getblo(n))
minn[i]=1e7, maxx[i]=-1;
rep(i, 1, n){
getmin(minn[getblo(i)], a[i]);
getmax(maxx[getblo(i)], a[i]);
}
}
signed main(){
input();
buildBlock();
int l, r, bl, br, mx, mn;
while(q--){
l=readin(1), r=readin(1), mx=-1, mn=1e7;
bl=getblo(l), br=getblo(r);
if(bl==br) rep(i, l, r) getmax(mx, a[i]), getmin(mn, a[i]);
else{
rep(i, l, getl(getblo(l)+1)-1)
getmax(mx, a[i]), getmin(mn, a[i]);
rep(i, getblo(l)+1, getblo(r)-1)
getmax(mx, maxx[i]), getmin(mn, minn[i]);
rep(i, getr(getblo(r)-1)+1, r)
getmax(mx, a[i]), getmin(mn, a[i]);
}
writc(mx-mn);
}
return 0;
}
◆ [CODECHEF]Chef and Churu
考虑对函数区间进行分块，在每个函数块中，维护每个位置对这个块的贡献。设每 \(L\) 个函数分成一块。并使用一个 \(\rm BIT\) 来维护前缀和。
当修改位置 \(p\) 时，暴力看 \(p\) 对每个块的影响函数数量是多少，打上标记即可。修改复杂度是 \(\mathcal O({N\over L}+\log N)\) 的。
询问的时候，不是整块的就暴力扫过每个函数并使用 \(\rm BIT\) 询问，是整块覆盖就直接块和加上标记即可，这部分复杂度是 \(\mathcal O(L\log N)\) 的
所以，总的复杂度是 \(\mathcal O(Q{N\over L}+QL\log N)\) 的，当 \(L=\sqrt {N\over \log N}\) 时复杂度最优，此时复杂度显然为 \(\mathcal O(Q\sqrt {N\log N})\).
但是实际上我们可以使用 \(\mathcal O(\sqrt n)\) 修改与 \(\mathcal O(1)\) 查询的方案维护原数列的和，这样修改的 \(\log\) 变成根号，但是询问的 \(\log\) 没有了，所以复杂度降为 \(\mathcal O(Q\sqrt N)\).
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define NDEBUG
#include<cassert>
namespace Elaina{
#define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
#define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
#define mmset(a, b) memset(a, b, sizeof a)
// #define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T>inline T fab(T x){ return x<0? -x: x; }
template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
template<class T>inline T readin(T x){
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template<class T>inline void writc(T x, char s='\n'){
static int fwri_sta[1005], fwri_ed=0;
if(x<0) putchar('-'), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
}
using namespace Elaina;
const int maxn=1e5;
const int celia=320;
inline int getblo(int x){ return (x-1)/celia+1; }
inline int getl(int id){ return (id-1)*celia+1; }
inline int getr(int id){ return id*celia; }
ull a[maxn+5];
int fl[maxn+5], fr[maxn+5], n;
namespace BIT{
#define lowbit(i) ((i)&(-(i)))
ll c[maxn+5];
inline void clear(){
rep(i, 1, n) c[i]=0;
}
inline void modify(int i, ull x){
assert(i!=0);
for(; i<=n; i+=lowbit(i))
c[i]+=x;
}
inline ull query(int i){
ull ret=0;
for(; i; i-=lowbit(i)) ret+=c[i];
return ret;
}
}
struct Block{
int times[maxn+5], l, r;
ull sum;
inline void build(){
BIT::clear();
rep(i, l, r){
BIT::modify(fl[i], 1);
BIT::modify(fr[i]+1, -1);
}
rep(i, 1, n){
times[i]=BIT::query(i);
sum+=1ll*times[i]*a[i];
}
}
inline void modify(int p, ull pre, ull v){
sum-=1ll*times[p]*pre;
sum+=1ll*times[p]*v;
}
inline ull query(int L, int R){
if(L<=l && r<=R) return sum;
ull ret=0;
rep(i, max(l, L), min(r, R))
ret+=BIT::query(fr[i])-BIT::query(fl[i]-1);
return ret;
}
}B[maxn/celia+5];
inline void input(){
n=readin(1);
rep(i, 1, n) a[i]=readin(1);
rep(i, 1, n) fl[i]=readin(1), fr[i]=readin(1);
}
inline void initialize(){
rep(i, 1, getblo(n)){
B[i].l=getl(i), B[i].r=min(getr(i), n);
B[i].build();
}
BIT::clear();
rep(i, 1, n) BIT::modify(i, a[i]);
}
inline void update(int p, ull v){
ull pre=a[p];
a[p]=v; // pay attention!
BIT::modify(p, -pre);
BIT::modify(p, v);
rep(i, 1, getblo(n))
B[i].modify(p, pre, v);
}
signed main(){
input();
initialize();
int q=readin(1), opt, x, y, l, r;
while(q--){
opt=readin(1);
if(opt==1){
x=readin(1), y=readin(1);
update(x, y);
}
else{
l=readin(1), r=readin(1);
int bl=getblo(l), br=getblo(r);
if(bl==br) writc(B[bl].query(l, r));
else{
ull ans=0;
ans=ans+B[bl].query(l, r);
rep(i, bl+1, br-1) ans=ans+B[i].query(l, r);
ans=ans+B[br].query(l, r);
writc(ans);
}
}
}
return 0;
}
◆ [SPOJ2940]Untitled Problem II
这道题稍微复杂一点，但是我由一个错误的思路很顺利地得到了正确思路的灵感：
这道题不就是序列分块之后直接维护块中最大值吗？修改的时候，如果是整块就打上标记，如果不是整块暴力改了再更新最大值就好啦？
但是这是错误的，至于为什么，因为这家伙是区间修改，而非单纯的单点修改，如果是单点修改当然可以这样做，但是区间会存在一个问题 —— 每个点的改变量为因为他们的下标不同而不同。
那这个题怎么做？我们考察一个修改 \((l, r, k)\) 造成的影响：
- 对于 \(i<l\) 的部分，没有影响；
- 对于 \(l\le i\le r\) 的部分，\(s'(i)=s(i)+(i-l+1)\times k=s(i)+ik+(1-l)k\)；
- 对于 \(i>r\) 的部分，\(s'(i)=s(i)+(r-l+1)\times k\)；
不难发现，有影响的部分的新值，都是形如 \(C+ik\) 的，它提示我们可以维护每个块中的 \(C,k\)，我们可以将其视作懒标记。
接下来考察答案，答案无非就是想让我们找到区间最大的 \(C+\max\{s(i)+ik\}\)，设 \(p=s(i)+ik\)，那么我们可以得到 \(s(i)=-ki+p\)，这引导我们往几何方向思考，如果我们将 \((i,s(i))\) 看作点，将 \(-k\) 看作斜率，这事实上就是在由一个块中所有 \((i,s(i))\) 构成的点集中，用 \(y=-k+C\) 这条线去切每个点，得到的最大的截距即为该块的 \(\max\).
这是个经典问题，我们可以维护一个上凸壳，当一个块被整体修改的时候，凸壳形态显然不变，当一个块部分修改时，则需要重构这个块的凸壳，使用叉乘判断即可。
时间复杂度 \(\mathcal O(n\sqrt n)\).
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
// #define NDEBUG
#include<cassert>
namespace Elaina{
#define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
#define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
#define mmset(a, b) memset(a, b, sizeof a)
// #define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T>inline T fab(T x){ return x<0? -x: x; }
template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
template<class T>inline T readin(T x){
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template<class T>inline void writc(T x, char s='\n'){
static int fwri_sta[1005], fwri_ed=0;
if(x<0) putchar('-'), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
}
using namespace Elaina;
const int maxn=50000;
const int celia=250;
inline int getblo(int x){ return (x-1)/celia+1; }
inline int getl(int id){ return (id-1)*celia+1; }
inline int getr(int id){ return celia*id; }
int a[maxn+5], n, q;
ll s[maxn+5];
struct block{
int L, R; ll k, c;
int sta[celia+5], ed;
inline ll calc(int x){ return 1ll*k*x+s[x]+c; }
inline ll query(){
int a, b;
if(!ed){ // rebuild the stack
for(int i=L; i<=R; ++i){
while(ed>=2){
a=sta[ed-1], b=sta[ed];
// cross multiplication
if(1ll*(b-a)*(s[i]-s[b])-1ll*(i-b)*(s[b]-s[a])<0) break;
--ed;
}
sta[++ed]=i;
}
}
int l=2, r=ed, mid;
while(l<=r){
mid=(l+r)>>1, a=sta[mid-1], b=sta[mid];
// compare the slope
if((s[b]-s[a])<-k*(b-a)) r=mid-1;
else l=mid+1;
}
return calc(sta[r]);
}
inline ll query(int l, int r){
if(l<=L && R<=r) return query();
ll ans=-1ll<<50;
rep(i, max(l, L), min(r, R))
ans=max(ans, calc(i));
return ans;
}
inline void modify(int l, int r, ll dk, ll dc){
if(l<=L && R<=r) return k+=dk, c+=dc, void();
ed=0; // put tag to rebuild
rep(i, max(l, L), min(r, R)) s[i]+=1ll*dk*i+dc;
}
}B[(maxn/celia)+5];
inline void input(){
n=readin(1);
rep(i, 1, n){
a[i]=readin(1);
s[i]=s[i-1]+a[i];
}
}
inline void buildBlock(){
for(int i=1; i<=getblo(n); ++i)
B[i].L=getl(i), B[i].R=min(getr(i), n);
}
signed main(){
input();
buildBlock();
q=readin(1);
int opt, l, r, bl, br;
while(q--){
opt=readin(1), l=readin(1), r=readin(1);
bl=getblo(l), br=getblo(r);
if(opt==1){
ll ans=-1ll<<50;
rep(i, getblo(l), getblo(r))
ans=max(ans, B[i].query(l, r));
writc(ans);
}
else{
ll dk=readin(1), dc;
dc=dk*(1-l);
rep(i, getblo(l), getblo(r))
B[i].modify(l, r, dk, dc);
dc=1ll*dk*(r-l+1);
dk=0;
rep(i, getblo(r+1), getblo(n))
B[i].modify(r+1, n, dk, dc);
}
}
return 0;
}
贰、给定值分块 ¶
该中题型，一般的类型是在一个静态数列上，给定动态询问，每个询问存在一个参数，该参数会影响暴力的复杂度。而在 这个参数较小的时候，又可以直接通过存储、暴力一类的手段解决，这便提示我们对于这个参数的不同大小分别做不同的算法。
◆ [CODECHEF]Children Trips
观察该题目的特性：
- 从一个点开始，贪心走最远到到达另一个端点，花费一定最优；
- 从两个点同时往中间开始走，花费一定最优；
有了这两个性质，我们就有了一个暴力的做法：
从两个点同时往 \(lca\) 爬，走到 \(lca\) 停下，返回花费；
但是这样存在一个小问题，我们不能直接爬到 \(lca\)，我们要看在回合之间，剩下的距离是否能够一次解决，即这种情况：
当 \(p=2\) 时，如果我们从两边分开往中间爬，那么花费会是 \(1+1=2\)，但是事实上它可以直接一步到位了。
不难发现，由于每条边的长度只可能是 \(1,2\)，所以当 \(p\) 比较大的时候，暴力一步一步爬也能很快到达 \(lca\)，这提示我们对 \(p\) 的范围进行分块。
当 \(p>\sqrt n\) 时，我们可以直接做暴力，那当 \(p\le \sqrt n\) 呢？
由于这样的 \(p\) 很少，我们可以考虑对于每个 \(p\)，处理出一个 \(portal(p,i,j)\) 表示从点 \(i\) 开始，往上走了 \(2^j\) 步（每步长度为 \(p\)）后到达的点，这类似于倍增 \(lca\) 的 \(tp(i,j)\) 数组，由于这个数组预处理是 \(\mathcal O(n\log n)\) 的，我们可以考虑对于相同的 \(p\) 预处理之后同时使用，将这种询问按照 \(p\) 排序即可，该部分复杂度为 \(\mathcal O(n\sqrt n\log n)\).
然后就完事了。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
// #define NDEBUG
#include<cassert>
namespace Elaina{
#define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
#define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
#define mmset(a, b) memset(a, b, sizeof a)
// #define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T>inline T fab(T x){ return x<0? -x: x; }
template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
template<class T>inline T readin(T x){
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template<class T>inline void writc(T x, char s='\n'){
static int fwri_sta[1005], fwri_ed=0;
if(x<0) putchar('-'), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
}
using namespace Elaina;
const int maxn=1e5;
const int logn=17;
const int celia=320;
int n, m;
vector<pii>g[maxn+5];
inline void add_edge(int u, int v, int w){
g[u].push_back({v, w}); g[v].push_back({u, w});
}
inline void input(){
n=readin(1);
int u, v, w;
rep(i, 2, n){
u=readin(1), v=readin(1), w=readin(1);
add_edge(u, v, w);
}
}
int tp[maxn+5][logn+5], dis[maxn+5], dep[maxn+5];
void dfs(int u, int par){
tp[u][0]=par, dep[u]=dep[par]+1;
rep(j, 1, logn) tp[u][j]=tp[tp[u][j-1]][j-1];
// for(const auto& [v, w]: g[u]) if(v!=par){
// dis[v]=dis[u]+w;
// dfs(v, u);
// }
for(auto e: g[u]) if(e.fi!=par){
dis[e.fi]=dis[u]+e.se;
dfs(e.fi, u);
}
}
inline int getLca(int u, int v){
if(dep[u]<dep[v]) swap(u, v);
drep(j, logn, 0) if(dep[tp[u][j]]>=dep[v])
u=tp[u][j];
if(u==v) return u;
drep(j, logn, 0) if(tp[u][j]!=tp[v][j])
u=tp[u][j], v=tp[v][j];
return tp[u][0];
}
struct query{ int u, v, p, id; };
vector<query>big, smal;
int ans[maxn+5];
inline void getQuery(){
m=readin(1);
int u, v, p;
for(int i=1; i<=m; ++i){
u=readin(1), v=readin(1), p=readin(1);
if(p<=celia) smal.push_back({u, v, p, i});
else big.push_back({u, v, p, i});
}
}
// get a node after jumping distance at @p w
inline int jump(int u, int w){
int now=dis[u];
drep(j, logn, 0) if(now-dis[tp[u][j]]<=w)
u=tp[u][j];
return u;
}
/** @return { residual distance, cost } */
inline pii bruteForce(int u, int goal, const int p){
if(u==goal) return {0, 0};
int cost=0, nxt;
while(u^goal){
nxt=jump(u, p);
if(dep[nxt]>dep[goal]) u=nxt, ++cost;
else return {dis[u]-dis[goal], cost};
}
return {dis[u]-dis[goal], cost};
}
/** the node where after @p u jump 2^j steps which length is @p p */
int portal[maxn+5][logn+5];
inline void buildPortal(const int p){
rep(i, 1, n) portal[i][0]=jump(i, p);
rep(j, 1, logn) rep(i, 1, n)
portal[i][j]=portal[portal[i][j-1]][j-1];
}
/**
* @return { residual distance, cost }
* @warning you should presolve array @p portal[][]
* */
inline pii trans(int u, int goal){
int cost=0;
drep(j, logn, 0) if(dep[portal[u][j]]>dep[goal]) // shouldn't be equal
cost+=1<<j, u=portal[u][j];
return {dis[u]-dis[goal], cost};
}
inline int solve(int u, int v, const int p){
if(u==v) return 0;
int lca=getLca(u, v);
pii left=(p<=celia? trans(u, lca): bruteForce(u, lca, p));
pii right=(p<=celia? trans(v, lca): bruteForce(v, lca, p));
return left.se+right.se+(left.fi+right.fi<=p? 1: 2);
}
inline void solveBig(){
// for(const auto& [u, v, p, id]: big)
// ans[id]=solve(u, v, p);
for(auto q: big) ans[q.id]=solve(q.u, q.v, q.p);
}
inline void solveSmall(){
auto cmp=[](const query& a, const query& b){ return a.p<b.p; };
sort(smal.begin(), smal.end(), cmp);
int pre_p=-1;
// for(const auto& [u, v, p, id]: smal){
// if(p!=pre_p) buildPortal(p);
// pre_p=p;
// ans[id]=solve(u, v, p);
// }
for(auto q: smal){
if(q.p!=pre_p) buildPortal(q.p);
pre_p=q.p;
ans[q.id]=solve(q.u, q.v, q.p);
}
}
signed main(){
input();
dfs(1, 0);
getQuery();
solveBig();
solveSmall();
rep(i, 1, m) writc(ans[i]);
return 0;
}
叁、各种莫队 ¶
莫队算法的特性，唔，就免了罢，但是不同的莫队特性还是较为鲜明的。
§ 普通莫队 §
普通？看上去很简单嘛，但事实上不只是它，许多莫队都可以和其他的一些数据结构同时使用，这个时候将会变得比较复杂。
◆ [PA2011]Kangaroos
考察两个区间 \([l,r],[l',r']\) 相交，这不禁让我们想起了跨立实验，这里，我们只要满足 \(l\le r'\;\land\;l'\le r\) 即可。
假设我们的询问区间是 \([l',r']\)，将符合条件的区间在某个序列上标成 \(1\)，不合法为 \(0\)（按照原下标），那么我们要找的就是与这个区间相交的所有区间中，构成的最大连续 \(1\) 段，我们不妨将区间端点放到一个序列上，那么一个询问的区间实际上就是这个序列上的某一段 \(l\) 前缀和 \(r\) 后缀，而当一个区间合法时，需要其 \(l,r\) 都在合法区间中，我们不难想到使用莫队+线段树，莫队处理询问，线段树处理最大连续段，复杂度 \(\mathcal O(n\sqrt n\log n)\)，不过应该也可以使用回滚莫队，不想想了，就算了。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
// #define NDEBUG
#include<cassert>
namespace Elaina{
#define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
#define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
#define mmset(a, b) memset(a, b, sizeof a)
// #define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T>inline T fab(T x){ return x<0? -x: x; }
template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
template<class T>inline T readin(T x){
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template<class T>inline void writc(T x, char s='\n'){
static int fwri_sta[1005], fwri_ed=0;
if(x<0) putchar('-'), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
}
using namespace Elaina;
const int maxn=5e4;
const int maxm=4e5;
const int celia=1000; // sqrt(n log n)
inline int getblo(int x){ return (x-1)/celia+1; }
inline int getl(int id){ return (id-1)*celia+1; }
inline int getr(int id){ return id*celia; }
namespace saya{
int mx[maxn<<2|2], mxl[maxn<<2|2], mxr[maxn<<2|2];
#define mid ((l+r)>>1)
#define ls (i<<1)
#define rs (i<<1|1)
#define _lq ls, l, mid
#define _rq rs, mid+1, r
#define _this i, l, r
inline void pushup(int i, int l, int r){
mx[i]=max(max(mx[ls], mx[rs]), mxr[ls]+mxl[rs]);
mxl[i]=(mxl[ls]==mid-l+1? mxl[ls]+mxl[rs]: mxl[ls]);
mxr[i]=(mxr[rs]==r-mid? mxr[rs]+mxr[ls]: mxr[rs]);
}
void modify(int p, int v, int i, int l, int r){
if(l==r){
mx[i]=mxl[i]=mxr[i]=v;
return;
}
if(p<=mid) modify(p, v, _lq);
else modify(p, v, _rq);
pushup(_this);
}
#undef mid
#undef ls
#undef rs
#undef _lq
#undef _rq
#undef _this
}
struct query{
int l, r, id;
inline bool operator <(const query& rhs) const{
return getblo(l)==getblo(rhs.l)? r<rhs.r: l<rhs.l;
}
}q[maxm+5];
int ans[maxm+5];
struct node{ int x, id, f;
inline bool operator <(const node& rhs) const{
return x==rhs.x? f<rhs.f: x<rhs.x;
}
}a[maxn*2+5];
int n, m, acnt;
inline void input(){
n=readin(1), m=readin(1);
int l, r;
rep(i, 1, n){
l=readin(1), r=readin(1);
a[++acnt]=node{l, i, 0}, a[++acnt]=node{r, i, 1};
}
sort(a+1, a+acnt+1);
}
inline void getquery(){
int l, r;
for(int i=1; i<=m; ++i){
q[i].l=readin(1), q[i].r=readin(1), q[i].id=i;
// find the pos where q[i].l >= a[pos]
q[i].l=lower_bound(a+1, a+acnt+1, node{q[i].l, 0, 0})-a;
// find the pos where q[i].r <= a[pos], so use this strange thing
q[i].r=lower_bound(a+1, a+acnt+1, node{q[i].r+1, 0, 0})-a-1;
}
}
// l <= r' and l' <= r, so the dimension should be opposite
inline void add(int i, int f){
if(a[i].f^f) saya::modify(a[i].id, 1, 1, 1, n);
}
inline void del(int i, int f){
if(a[i].f^f) saya::modify(a[i].id, 0, 1, 1, n);
}
inline void captainMo(){
sort(q+1, q+m+1);
int l=1, r=0;
rep(i, 1, m){
while(l>q[i].l) add(--l, 0);
while(r<q[i].r) add(++r, 1);
while(l<q[i].l) del(l++, 0);
while(r>q[i].r) del(r--, 1);
// while (l > q[i].l) add (-- l,0);
// while (r < q[i].r) add (++ r,1);
// while (l < q[i].l) del (l ++,0);
// while (r > q[i].r) del (r --,1);
ans[q[i].id]=saya::mx[1];
}
}
inline void print(){
rep(i, 1, m) writc(ans[i]);
}
signed main(){
// freopen("12.in", "r", stdin);
// freopen("shit.out", "w", stdout);
input();
getquery();
captainMo();
print();
return 0;
}
§ 树上莫队 §
询问树上两点路径之间的一些东西。
将树上的点的 \(\rm Euler\) 序得到（就是进入、退出各放一次），然后在这个序列上做普通莫队就行了。
为什么可行？如果我们严格按照入点、出点顺序加入、删除每个点，那么最后端点指针正确时，莫队维护的数据中就只会剩下路径上的点的信息了。
唯一需要注意的就是，设置端点的时候，要注意是哪个点的 \(in/out\) 当左端点，哪个点的 \(in/out\) 当右端点。
◆ [SPOJ10707]Count on a tree
树上莫队板题，就不说了。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
// #define NDEBUG
#include<cassert>
namespace Elaina{
#define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
#define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
#define mmset(a, b) memset(a, b, sizeof a)
// #define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T>inline T fab(T x){ return x<0? -x: x; }
template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
template<class T>inline T readin(T x){
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template<class T>inline void writc(T x, char s='\n'){
static int fwri_sta[1005], fwri_ed=0;
if(x<0) putchar('-'), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
}
using namespace Elaina;
const int maxn=40000;
const int maxm=1e5;
const int celia=290;
inline int getblo(int x){ return (x-1)/celia+1; }
vector<int>g[maxn+5];
int n, m, a[maxn+5];
inline void add_edge(int u, int v){
g[u].push_back(v), g[v].push_back(u);
}
inline void input(){
n=readin(1), m=readin(1);
rep(i, 1, n) a[i]=readin(1);
int u, v;
rep(i, 1, n-1){
u=readin(1), v=readin(1);
add_edge(u, v);
}
}
int tmp[maxn+5];
inline void getHash(){
rep(i, 1, n) tmp[i]=a[i];
sort(tmp+1, tmp+n+1);
int siz=unique(tmp+1, tmp+n+1)-tmp-1;
rep(i, 1, n) a[i]=lower_bound(tmp+1, tmp+siz+1, a[i])-tmp;
}
int in[maxn+5], out[maxn+5];
int dep[maxn+5], fa[maxn+5], siz[maxn+5], wson[maxn+5];
int dfn[maxn*2+5], refl[maxn*2+5], dcnt;
void dfs(int u, int par){
dfn[++dcnt]=u, in[u]=dcnt, refl[dcnt]=u;
dep[u]=dep[par]+1, fa[u]=par, siz[u]=1;
for(int v: g[u]) if(v!=par){
dfs(v, u), siz[u]+=siz[v];
if(siz[v]>siz[wson[u]])
wson[u]=v;
}
dfn[++dcnt]=u, out[u]=dcnt, refl[dcnt]=u;
}
int tp[maxn+5];
void dfs2(int u){
if(!wson[u]) return;
tp[wson[u]]=tp[u]; dfs2(wson[u]);
for(int v: g[u]) if(v!=wson[u] && v!=fa[u])
dfs2(tp[v]=v);
}
inline int getLca(int u, int v){
while(tp[u]^tp[v]){
if(dep[tp[u]]<dep[tp[v]]) swap(u, v);
u=fa[tp[u]];
}
return dep[u]<dep[v]? u: v;
}
struct query{
int l, r, lca, id;
inline bool operator <(const query rhs) const{
if(getblo(l)==getblo(rhs.l)) return r<rhs.r;
return getblo(l)<getblo(rhs.l);
}
}q[maxm+5];
int ans[maxm+5];
inline void getQuery(){
int u, v, lca;
rep(i, 1, m){
u=readin(1), v=readin(1);
if(in[u]>in[v]) swap(u, v);
lca=getLca(u, v);
if(lca==u) q[i]={in[u], in[v], 0, i};
else q[i]={out[u], in[v], lca, i};
// printf("q[%d] :> (%d, %d, %d, %d)\n", i, out[u], in[v], lca, i);
}
}
int cnt[maxn+5], used[maxn+5], cur;
inline void add(int i){
if(++cnt[a[i]]==1) ++cur;
}
inline void del(int i){
if(--cnt[a[i]]==0) --cur;
}
inline void extend(int i){
if(!used[i]) add(i); else del(i);
used[i]^=1;
}
inline void captainMo(){
sort(q+1, q+m+1);
int l=1, r=0, u, v, lca;
rep(i, 1, m){
while(r<q[i].r) extend(refl[++r]);
while(r>q[i].r) extend(refl[r--]);
while(l<q[i].l) extend(refl[l++]);
while(l>q[i].l) extend(refl[--l]);
if(q[i].lca) extend(q[i].lca);
ans[q[i].id]=cur;
if(q[i].lca) extend(q[i].lca);
}
}
inline void print(){
rep(i, 1, m) writc(ans[i]);
}
signed main(){
input();
getHash();
dfs(1, 0);
// rep(i, 1, dcnt) writc(dfn[i], ' '); Endl;
dfs2(tp[1]=1);
getQuery();
captainMo();
print();
return 0;
}
§ 回滚莫队 §
当某种数据只方便加入或者只方便删除时，可以考虑使用它。
◆ [CODECHEF]Chef and Problems
其实和洛谷上的回滚莫队板题是一个意思。
我们考虑往序列中加入元素时，我们可以很好维护其最左、最右出现位置，但是要删除它的时候似乎就变得困难。考虑如何避免删除。
对于左端点位于同一区间的询问，我们可以使他们的右端点单调，这样右端点的移动肯定只有加入，但是对于左端点，我们考虑移动到当前询问的位置之后再将其移动回所属区间的右端点位置，这样下一次询问又只有加入了。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define NDEBUG
#include<cassert>
namespace Elaina{
#define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
#define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
#define mmset(a, b) memset(a, b, sizeof a)
// #define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T>inline T fab(T x){ return x<0? -x: x; }
template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
template<class T>inline T readin(T x){
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template<class T>inline void writc(T x, char s='\n'){
static int fwri_sta[1005], fwri_ed=0;
if(x<0) putchar('-'), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
}
using namespace Elaina;
const int maxn=1e5;
const int maxm=1e5;
const int celia=320;
inline int getblo(int x){ return (x-1)/celia+1; }
inline int getl(int id){ return (id-1)*celia+1; }
inline int getr(int id){ return id*celia; }
struct query{
int l, r, id;
inline bool operator <(const query& rhs) const{
if(getblo(l)==getblo(rhs.l)) return r<rhs.r;
return l<rhs.l;
}
}q[maxm+5];
int res[maxm+5];
int a[maxn+5], n, m, k;
inline void input(){
n=readin(1), readin(1), m=readin(1);
rep(i, 1, n) a[i]=readin(1);
int l, r;
rep(i, 1, m){
l=readin(1), r=readin(1);
q[i]=query{l, r, i};
}
}
int tmp[maxn+5];
inline void getHash(){
rep(i, 1, n) tmp[i]=a[i];
sort(tmp+1, tmp+n+1);
int siz=unique(tmp+1, tmp+n+1)-tmp-1;
rep(i, 1, n) a[i]=lower_bound(tmp+1, tmp+siz+1, a[i])-tmp;
// rep(i, 1, n) printf("a[%d] == %d\n", i, a[i]);
}
int lst[maxn+5]; // assistant array
inline int bruteForce(int l, int r){
// printf("bruteForce :> l == %d, r == %d\n", l, r);
int ret=0;
rep(i, l, r) lst[a[i]]=-1;
rep(i, l, r){
if(!~lst[a[i]]) lst[a[i]]=i;
ret=max(ret, i-lst[a[i]]);
}
// printf("finished!\n");
return ret;
}
int cls[maxn+5], clcnt; // record the array that need to be cleared
int mxpos[maxn+5], mnpos[maxn+5];
inline void captainMo(){
mmset(mxpos, -1); mmset(mnpos, -1);
for(int i=1, j=1; i<=n && j<=getblo(n); ++j){
// @p j enumerate the interval which left endpoint belongs to
int br=min(n, getr(j)), l=br+1, r=br, ans=0;
clcnt=0;
// printf("Now j == %d\n", j);
for(; i<=m && getblo(q[i].l)==j; ++i){
// printf("i == %d, j == %d\n", i, j);
if(getblo(q[i].r)==j)
res[q[i].id]=bruteForce(q[i].l, q[i].r);
else{
// printf("into else!\n");
while(r<q[i].r){
++r;
mxpos[a[r]]=r;
if(!~mnpos[a[r]]) mnpos[a[r]]=r, cls[++clcnt]=a[r];
ans=max(ans, r-mnpos[a[r]]);
}
int rec_ans=ans;
while(l>q[i].l){
--l;
if(~mxpos[a[l]]) ans=max(ans, mxpos[a[l]]-l);
else mxpos[a[l]]=l; // the rightmost endpoint may appeared at left interval
}
res[q[i].id]=ans;
while(l<=br){
// restore the data which is updated by left interval
if(mxpos[a[l]]==l) mxpos[a[l]]=-1;
++l;
}
ans=rec_ans;
}
}
// printf("out!\n");
for(int k=1; k<=clcnt; ++k)
mxpos[cls[k]]=mnpos[cls[k]]=-1;
}
}
inline void print(){
rep(i, 1, m) writc(res[i]);
}
signed main(){
// freopen("P5906_1.in", "r", stdin);
// freopen("P5906_1.out", "w", stdout);
input();
getHash();
sort(q+1, q+m+1);
// printf("shit!\n");
captainMo();
print();
return 0;
}