标签 data structures 下的文章

「codeforces - 1555F」Good Graph

31-07-2021
笔记
0 comment

来一个不用 HLD / LCT 的做法。~~其实没有什么本质上的差别~~

首先容易想到离线，并且满足条件的图一定是边仙人掌，我们把离线后得到的图缩点，形成一片森林，并且标记树边。树边显然必选，主要来看非树边。

维护 $pre(x)$ 表示从根到 $x$ 的边权异或和，设当前我们考虑的非树边是 $(x,y)$，那么如果 $x,y$ 已经处于同一个环里或者 $pre(x)\oplus pre(y)\oplus w(x,y)\neq1$ 是不行的，否则就可以加进去。

然后怎么实现查找是否在同一个环里之类的就用 time-stamp & BIT 解决。

#include<bits/stdc++.h>
using namespace std;
const int N=300100,M=500100;
int n,m,ix[M],iy[M],iw[M],sjc,fa[20][N],indfn[N],outdfn[N],tag[M],dep[N],pre[N];
vector<pair<int,int>> G[N];
void dfs(int x,int las)
{
    fa[0][x]=las;
    indfn[x]=++sjc;
    dep[x]=dep[las]+1;
    for(int i=1; i<20; ++i) fa[i][x]=fa[i-1][fa[i-1][x]];
    for(auto [y,w]:G[x])    if(y!=las)    pre[y]=pre[x]^w,dfs(y,x);
    outdfn[x]=sjc;
}
int fwk[N];
void ins(int x,int y) { for(; x<=n; x+=x&-x)    fwk[x]+=y; }
int find(int x)
{
    int res=0;
    for(; x; x-=x&-x)  res+=fwk[x];
    return res;
}
int lh[N];
int dsuFind(int x)
{
    while(x!=lh[x])    x=lh[x]=lh[lh[x]];
    return x;
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y])    swap(x,y);
    for(int i=19; ~i; --i)    if(dep[fa[i][x]]>=dep[y])    x=fa[i][x];
    if(x==y)    return x;
    for(int i=19; ~i; --i)    if(fa[i][x]!=fa[i][y])    x=fa[i][x],y=fa[i][y];
    return fa[0][x];
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m;
    iota(lh+1,lh+n+1,1);
    for(int i=1; i<=m; ++i)
    {
        cin>>ix[i]>>iy[i]>>iw[i];
        int x=dsuFind(ix[i]),y=dsuFind(iy[i]);
        if(x!=y)
        {
            G[ix[i]].emplace_back(iy[i],iw[i]);
            G[iy[i]].emplace_back(ix[i],iw[i]);
            tag[i]=1,lh[x]=y;
        }
    }
    for(int i=1; i<=n; ++i)    if(!dep[i])    dfs(i,0);
    for(int i=1; i<=m; ++i)
    {
        if(tag[i])    cout<<"YES\n";
        else
        {
            int x=ix[i],y=iy[i];
            if(find(indfn[x])+find(indfn[y])-find(indfn[LCA(x,y)])*2>0||(pre[x]^pre[y]^iw[i])!=1)    cout<<"NO\n";
            else
            {
                cout<<"YES\n";
                while(x!=y)    (dep[x]<dep[y])&&(x^=y^=x^=y),ins(indfn[x],1),ins(outdfn[x]+1,-1),x=fa[0][x];
            }
        }
    }
    return 0;
}

Description

Link.

给出一棵树，初始边权为 $0$，支持毛毛虫虫体赋 $1$，虫足赋 $0$，以及查询路径边权和操作，$n,m\leqslant 10^5$。

Solution

立马想到按时间染色，那么判定一条边 $(u,v)$ 为重边的充要条件即 $col(u)=col(v)$（初始每个节点的颜色为 $1,\dots,n$）。

然后修改就转化为链覆盖，查询就成了查询区间相邻颜色相同二元组个数。HLD & 线段树可以解决。

说一下线段树的维护方法，维护区间左端点颜色、右端点颜色以及相邻颜色相同二元组个数（还有区间覆盖懒标）。向上 / 下更新均显。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++);
char buf[1<<21],*p1=buf,*p2=buf;
inline ll read() {
    ll x=0,f=0; char ch=getchar();
    while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
    return f?-x:x;
}
const int N=100100;
vector<int> G[N];
int n,m,dep[N],son[N],top[N],fa[N],sz[N],dfn[N],sjc,ton[N],col[N],cnt;
struct node { int lc,rc,num,tag; } tr[N*4],emp;
void push_up(int now) {
    tr[now].lc=tr[now<<1].lc;
    tr[now].rc=tr[now<<1|1].rc;
    tr[now].num=tr[now<<1].num+tr[now<<1|1].num+(tr[now<<1].rc==tr[now<<1|1].lc);
}
void push_down(int now,int l,int r) {
    if(!tr[now].tag) return;
    int mid=(l+r)>>1;
    tr[now<<1].num=mid-l,tr[now<<1|1].num=r-mid-1;
    tr[now<<1].lc=tr[now<<1|1].lc=tr[now].tag;
    tr[now<<1].rc=tr[now<<1|1].rc=tr[now].tag;
    tr[now<<1].tag=tr[now<<1|1].tag=tr[now].tag;
    tr[now].tag=0;
}
void build(int l,int r,int now) {
    tr[now]=emp;
    if(l==r) return ++cnt,tr[now]=node{cnt,cnt,0,0},void();
    int mid=(l+r)>>1;
    build(l,mid,now<<1),build(mid+1,r,now<<1|1);
    push_up(now);
}
void ins(int l,int r,int now,int x,int y,int v) {
    if(l>y||r<x) return;
    if(l>=x&&r<=y) return tr[now].tag=tr[now].lc=tr[now].rc=v,tr[now].num=r-l,void();
    int mid=(l+r)>>1;
    push_down(now,l,r);
    ins(l,mid,now<<1,x,y,v),ins(mid+1,r,now<<1|1,x,y,v);
    push_up(now);
}
int find0(int l,int r,int now,int x,int y) {
    if(l>=x&&r<=y) return tr[now].num;
    int mid=(l+r)>>1,res=0;
    push_down(now,l,r);
    if(mid>=x) res+=find0(l,mid,now<<1,x,y);
    if(mid<y) res+=find0(mid+1,r,now<<1|1,x,y);
    return res+(x<=mid&&y>mid&&tr[now<<1].rc==tr[now<<1|1].lc);
}
int find1(int l,int r,int now,int x) {
    if(l==r) return tr[now].lc;
    int mid=(l+r)>>1;
    push_down(now,l,r);
    return mid>=x?find1(l,mid,now<<1,x):find1(mid+1,r,now<<1|1,x);
}
void clear(int l,int r,int now) {
    tr[now]=emp;
    if(l==r) return;
    int mid=(l+r)>>1;
    clear(l,mid,now<<1),clear(mid+1,r,now<<1|1);
}
signed main() {
    function<void(int,int)> dfs0=[&](int x,int las) {
        fa[x]=las,dep[x]=dep[las]+1,sz[x]=1;
        for(int y:G[x]) if(y!=las) dfs0(y,x),sz[x]+=sz[y],(sz[y]>sz[son[x]])&&(son[x]=y);
    };
    function<void(int,int,int)> dfs1=[&](int x,int las,int t) {
        top[x]=t,ton[dfn[x]=++sjc]=x;
        if(son[x]) dfs1(son[x],x,t);
        for(int y:G[x]) if(y!=las&&y!=son[x]) dfs1(y,x,y);
    };
    for(int Case=read(); Case; --Case) {
        n=read(),m=read();
        for(int i=1,x,y; i<n; ++i) x=read(),y=read(),G[x].push_back(y),G[y].push_back(x);
        dfs0(1,0),dfs1(1,0,1),build(1,n,1);
        for(int t,x,y; m; --m) {
            t=read(),x=read(),y=read();
            if(t==1) {
                ++cnt;
                while(top[x]!=top[y]) {
                    if(dep[top[x]]<dep[top[y]]) swap(x,y);
                    ins(1,n,1,dfn[top[x]],dfn[x],cnt);
                    x=fa[top[x]];
                }
                if(dep[x]>dep[y]) swap(x,y);
                ins(1,n,1,dfn[x],dfn[y],cnt);
            } else {
                int res=0;
                while(top[x]!=top[y]) {
                    if(dep[top[x]]<dep[top[y]]) swap(x,y);
                    res+=find0(1,n,1,dfn[top[x]],dfn[x])+(find1(1,n,1,dfn[top[x]])==find1(1,n,1,dfn[fa[top[x]]]));
                    x=fa[top[x]];
                }
                if(dep[x]>dep[y]) swap(x,y);
                res+=find0(1,n,1,dfn[x],dfn[y]);
                printf("%d\n",res);
            }
        }
        for(int i=1; i<=n; ++i) dep[i]=son[i]=top[i]=fa[i]=sz[i]=dfn[i]=ton[i]=0,G[i].clear();
        sjc=cnt=0,clear(1,n,1);
    }
    return 0;
}

「ARC 124A」LR Constraints

Link.

我们可以把 $1\sim n$ 个盒子里能放的球的编号集合全部求出来。然后就直接来。

注意题目已经给出了 $k$ 个球的位置，所以「Note that for each integer $i$ from $1$ through $K$, there must be at least one card on which we write $i$.」这个限制不用管。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define len(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N=1100,MOD=998244353;
int n,k,ts[N],tek[N],fin[N],Rs[N];
set<int> rs[N];
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>k,memset(fin,-1,sizeof fin);
    for(int i=1; i<=k; ++i) {
        char c; cin>>c;
        ts[i]=(c=='R');
        cin>>tek[i];
        Rs[tek[i]]=ts[i];
    }
    for(int i=1; i<=k; ++i) {
        if(~fin[tek[i]]) return puts("0"),0;
        fin[tek[i]]=i;
    }
    for(int i=1; i<=n; ++i) {
        if(~fin[i]) rs[i].emplace(fin[tek[i]]);
        else {
            auto &s=rs[i];
            for(int j=1; j<=k; ++j) s.emplace(j);
            int tmp=0;
            for(int j=i+1; j<=n; ++j) {
                if(!Rs[j]) s.erase(fin[j]);
            }
            for(int j=1; j<i; ++j) {
                if(Rs[j]) s.erase(fin[j]);
            }
        }
    }
    int res=1;
    for(int i=1; i<=n; ++i) res*=len(rs[i]),res%=MOD;
    cout<<res<<"\n";
    return 0;
}

「ARC 124B」XOR Matching 2

Link.

预处理出 $s(i,j)=a_{i}\oplus b_{j}$，以及 $pos(i,x)$ 表示第 $i$ 层值 $x$ 的出现集合，用 std::map 均摊 $\mathcal{O}(n^{2})$ 空间。然后我们在第一层逐列考虑，对于第一层的每一种异或值，找出在每一行出现的位置集合，如果某一行没有出现就不行。最后就看集合大小是否等于 $n$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define int ll
const int N=2100;
int a[N],b[N],xr[N][N],n;
multimap<int,int> mp[N];
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n;
    for(int i=1; i<=n; ++i) cin>>a[i];
    for(int i=1; i<=n; ++i) cin>>b[i];
    for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) xr[i][j]=(a[i] xor b[j]),mp[i].insert({xr[i][j],j});
    vector<int> res;
    for(int j=1; j<=n; ++j) {
        bool ok=0;
        set<int> S;
        for(int i=1; i<=n; ++i) {
            auto rg=mp[i].equal_range(xr[1][j]);
            if(mp[i].find(xr[1][j])!=mp[i].end()) {
                for(auto it=rg.first; it!=rg.second; ++it) {
                    S.emplace(it->second);
                }
            }
            else {
                ok=1;
                break;
            }
        }
        if(ok) continue;
        if(S.size()==n) {
            res.push_back(xr[1][j]);
        }
    }
    sort(all(res));
    res.erase(unique(all(res)),res.end()); 
    cout<<res.size()<<"\n";
    for(int x:res) cout<<x<<"\n";
    return 0;
}

「ARC 124C」LCM of GCDs

Link.

考场做法复杂度有问题啊，虽然屮过去了。有空来补 official editorial 做法。

// Oops, something went wrong.

「ARC 124D」Yet Another Sorting Problem

Link.

~~你看 ARC 又考置换群了。震撼围观吴老师精确押题。~~

套路题，连边 $i\rightarrow p_{i}$ 后一堆环摆出来。答案是

$$ n+m-(\text{the number of cycles in the graph})+\\ 2\times\max\{\text{the number of cycles of size of 2 or greater consisting of vertice numbered through }1\text{ to }n,\\ \text{the number of cycles of size of 2 or greater consisting of vertice numbered through }n+1\text{ to }n+m\} $$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int N=200100;
int n,m,p[N],vis[N];
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m; int x0=0,x1=0,res=n+m,ls=0;
    for(int i=1; i<=n+m; ++i) cin>>p[i];
    for(int i=1; i<=n+m; ++i) {
        if(vis[i]) continue;
        int now=i,len=0,qwq=0,qaq=0;
        while(!vis[now]) {
            ++len;
            if(now<=n) qwq=1;
            else qaq=1;
            vis[now]=1;
            now=p[now];
        }
        if(!qaq&&len>=2) ++x0;
        if(!qwq&&len>=2) ++x1;
        --res;
    }
    cout<<res+2*max(x0,x1)<<"\n";
    return 0;
}

「ARC 124E」Pass to Next

Link.

「ARC 124F」Chance Meeting

Link.

Solution -「营业」「CF 527C」Glass Carving

08-07-2021
笔记
0 comment

Description

Link.

有一个块 $n\times m$ 的矩形，有 $q$ 次操作，每次把矩形横 / 竖着切一刀，问切完后的最大矩形面积。

Solution

一个不同于大多数人、总时间复杂度 $\mathcal{O}(n\log_{2}n)$，每次回答 $\mathcal{O}(\alpha(n))$ 的做法，瓶颈在排序。

显然答案是最大行列相乘。首先我们把询问离线，然后逆序处理。你发现这相当于把切开变成了合并，最大值不降，于是可以直接维护。

具体来说就是维护两个并查集，分别是行和列，然后再维护集合内元素个数，然后就直接合并。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
    return f?-x:x;
}
const int N=200100;
signed main() {
    int m=read(),n=read(),q=read();
    static int far[N],fac[N],szr[N],szc[N];
    iota(far+1,far+m+1,1);
    iota(fac+1,fac+n+1,1);
    for(int i=1;i<=m;++i) szr[i]=1;
    for(int i=1;i<=n;++i) szc[i]=1;
    auto findr=[&](int x) {while(x!=far[x]) x=far[x]=far[far[x]]; return x;};
    auto findc=[&](int x) {while(x!=fac[x]) x=fac[x]=fac[fac[x]]; return x;};
    auto merger=[&](int x,int y) {x=findr(x),y=findr(y); (x!=y)&&(szr[y]+=szr[x],szr[x]=0,far[x]=y);};
    auto mergec=[&](int x,int y) {x=findc(x),y=findc(y); (x!=y)&&(szc[y]+=szc[x],szc[x]=0,fac[x]=y);};
    static int op[N],X[N];
    vector<int> hx,vx;
    for(int i=1; i<=q; ++i) {
        char Op[4];
        scanf("%s",Op);
        op[i]=Op[0]=='H';
        X[i]=read();
        (op[i])&&(X[i]=n-X[i]);
        (op[i])&&(hx.push_back(X[i]),1);
        (!op[i])&&(vx.push_back(X[i]),1);
    }
    sort(hx.begin(),hx.end());
    sort(vx.begin(),vx.end());
    hx.insert(hx.begin(),0);
    vx.insert(vx.begin(),0);
    hx.push_back(n);
    vx.push_back(m);
    for(unsigned int i=1; i<hx.size(); ++i)
        for(int j=hx[i-1]+2; j<=hx[i]; ++j) mergec(j-1,j);
    for(unsigned int i=1; i<vx.size(); ++i)
        for(int j=vx[i-1]+2; j<=vx[i]; ++j) merger(j-1,j);
    ll mxr=0,mxc=0;
    for(int i=1; i<=m; ++i) mxr=max(mxr,(ll)szr[findr(i)]);
    for(int i=1; i<=n; ++i) mxc=max(mxc,(ll)szc[findc(i)]);
    vector<ll> ans;
    ans.push_back(mxr*mxc);
    for(int i=q; i>1; --i) {
        if(op[i]) mergec(X[i]+1,X[i]),mxc=max(mxc,(ll)szc[findc(X[i])]);
        else merger(X[i],X[i]+1),mxr=max(mxr,(ll)szr[findr(X[i])]);
        ans.push_back(mxr*mxc);
    }
    reverse(ans.begin(),ans.end());
    for(ll x:ans) printf("%lld\n",x);
    return 0;
}

Solution -「NOI 2020」时代的眼泪

26-06-2021
笔记
0 comment

Description

Link。

给出一个二维平面以及一些点，保证点不在同行 / 同列。每次询问求出一个子矩阵里面的顺序对。

Solution

卡常，卡你吗。

膜拜 dX。
基本是把 dX 的题解贺了过来所以没啥参考的价值。
不过有很多细节的处理不一样，大概能算个 $\frac{1}{50}$ 成新？

对序列分块，把贡献分成整块 - 散块 / 整块 - 整块/ 散块 - 整块 / 散块 - 散块以及散块内部 / 整块内部共六种贡献。

记 $\textit{ans}_{0}(l,r,x,y)$ 为询问 $l,r,x,y$ 的答案。

同时预处理出 $\textit{lb}(i,j),\textit{ub}(i,j)$ 分别表示在块 $i$ 中数 $j$ 的 std::lower_bound / std::upper_bound 值，下文如果写成单元函数的形式那么就是省去了第一维。

以及预先做一个块内排序，记为 $\textit{ord}(i,j)$，表示块 $i$ 中排序后的第 $j$ 个元素。

注意本文在每个 subtask 定义的东西在其他 subtask 依然适用。

散块 - 散块；

两边的都是 $\sqrt{n}$ 级别，拉出来分别排序后归并计算顺序对即可。

散块内部

考虑如何对 $\textit{ans}_{0}(l,r,x,y)$ 进行容斥。

主要矛盾集中在：会出现 $(a\in[1,x),b\in[x,y])$ 这样的贡献。令 $\textit{cnt}_{0}(i,j)$ 表示 $[\textit{lp},i]$ 中 $\textit{rank}_{1}$ 小于 $j$ 的数的数量，其中 $\textit{lp}$ 是当前块的左端点，下同，如果出现 $\textit{rp}$ 同理，$\textit{rank}_{1}$ 的定义见下文。

则容斥可以写为 $\textit{ans}_{0}(l,r,x,y)=\textit{ans}_{0}(l,r,1,y)-\textit{ans}_{0}(l,r,1,x-1)-\sum_{i=l}^{r}[a_{i}\in[x,y]]\cdot\textit{cnt}_{0}(i,\textit{lb}(x)-1)$。

又有 $\textit{ans}_{0}(l,r,1,x)=\sum_{i=l}^{r}[a_{i}\leqslant x]\cdot\textit{cnt}_{0}(i,\textit{rank}_{1}(i))$，我们就可以做到单次 $\mathcal{O}(\sqrt{n})$，注意的 $l,r$ 触及散块边界者不同时，对 $\textit{cnt}_{0}$ 的容斥也有区别。

整块 - 整块

令 $\textit{cnt}_{1}(i,j)$ 为块 $[1,i]$ 中 $\leqslant j$ 的元素个数，$\textit{ans}_{1}(L,R,x,y)$ 为块 $[L,R]$ 的答案，以及 $\textit{rank}_{0}(i,j)$ 是块 $i$ 中排名 $j$ 的元素在原数组中的下标。

我们掏出传统容斥：$\textit{ans}_{1}(L,R,x,y)=\textit{ans}_{1}(L,R,1,y)-\textit{ans}_{1}(L,R,1,x-1)-\sum_{i=L}^{R}P_{i}Q_{i}$，$P_{i}$ 是块 $[L,i)$ 中 $<x$ 的元素个数，$Q_{i}$ 是块 $i$ 种 $\in[x,y]$ 的元素个数。

考虑算 $\textit{ans}_{1}(L,R,1,x)$。

定义 $\textit{rank}_{1}(i,j)$ 为块 $i$ 中第 $j$ 个元素的排名（从小到大，下同），$\textit{rank}_{2}(i,j)$ 为块 $i$ 中满足 $<j$ 的最大元素的排名，$\textit{pre}_{b}(i,j)$ 为块 $[i,j]$ 中所有 $<\textit{rank}_{1}(i,j)$ 的元素数量。

易知 $\textit{pre}_{b}(i,j)=\textit{cnt}_{1}(i,\textit{rank}_{1}(i,j)-1)$，再定义 $\overset{\sqrt{n},\sqrt{n},\sqrt{n}}{\textit{cp}_{0}(i,L,r)}$ 为块 $[1,L]$ 与块 $i$ 前 $r$ 小的元素组成的顺序对数量，同样易知 $\textit{cp}_{0}(i,L,r)=\sum_{k\in T}[\textit{rank}_{1}(i,k)\leqslant r]\cdot\textit{pre}_{b}(L,\textit{rank}_{1}(i,k))$，其中 $T$ 是块 $i$ 的元素集。但这样搞状态数 $\mathcal{O}(n\sqrt{n})$ 转移还要 $\mathcal{\sqrt{n}}$ 而且不好前缀和。

不过可以发现使用 $\textit{ord}$ 数组 $\textit{cp}_{0}$ 就可以递推了：$\textit{cp}_{0}(i,L,r)=\sum_{k=lp}^{r+lp-1}\textit{pre}_{b}(L,k)=\textit{cp}_{0}(i,L,r-1)+\textit{pre}_{b}(L,r+lp-1)$。

然后 $\textit{ans}_{1}(L,R,1,x)=\sum_{i=L+1}^{R}\textit{cp}_{0}(i,i-1,\textit{rank}_{2}(i,x))-\textit{cp}_{0}(i,L-1,\textit{rank}_{2}(i,x))$。

预处理 $\textit{cp}_{0}$ 是 $\mathcal{O}(n\sqrt{n})$，单次回答 $\mathcal{O}(\sqrt{n})$。

散块 - 整块

枚举散块里面的元素，利用 $\textit{cnt}_{1}(i,j)$ 计算答案。

具体是令散块元素集为 $T$，整块编号为 $L,R$， $\sum_{i\in T}\textit{cnt}_{1}(R,i)-\textit{cnt}_{1}(L-1,i)$。

整块 - 散块

和上面有什么区别吗？

整块内部

预处理数组 $\overset{\sqrt{n},\sqrt{n},\sqrt{n}}{\textit{cp}_{1}(i,x,y)}$ 表示取 $\textit{ord}(i,x\dots y)$ 组成的序列的顺序对数量。

用 $\textit{rank}_{0}$ 来预处理：$\textit{cp}_{1}(i,x,y)=\textit{cp}_{1}(i,x,y-1)+\textit{cnt}_{0}(\textit{rank}_{0}(i,y),y-1)-\textit{cnt}_{0}(\textit{rank}_{0}(i,y),x-1)$。

综上，这个问题得以一个 $\mathcal{O}(n\sqrt{n})$ 的在线算法解决。

代码也是抄的 dX，像个 shit 一样就折叠了。

//almost copied from dead_X sry
//kouhu has no qiantu
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int Read()
{
    int x=0;char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0' && c<='9') x=x*10+(c&15),c=getchar();
    return x;
}
const int N=101111,A=460,BS=A+10;
ll cp0[BS][BS][BS];
int a[N],rk0[BS][BS],cnt0[BS][N],cp1[BS][BS][BS],lb[BS][N],rk1[N],cnt1[BS][N],L[BS],R[BS];
bool cmp(int x,int y) { return a[x]<a[y]; }
namespace IO{
    const int sz=1<<22;
    char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
    inline char gc(){
        return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
    }
    template<class T> void gi(T& x){
        x=0; char c=gc();
        for(;c<'0'||c>'9';c=gc());
        for(;c>='0'&&c<='9';c=gc())
            x=(x<<3)+(x<<1)+(c-'0');
    }
    inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
    inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
    template<class T> void pi(T x,char c='\n'){
        if(x<0) x=-x;
        if(x==0) pc('0'); int t=0;
        for(;x;x/=10) p[++t]=x%10+'0';
        for(;t;--t) pc(p[t]); pc(c);
    }
    struct F{~F(){flush();}}f; 
}
using IO::gi;
using IO::pi;
inline int read() { int r; gi(r); return r; }
int main(){
#ifdef ONLINE_JUDGE
    freopen("tears.in","r",stdin);
    freopen("tears.out","w",stdout);
#endif
    int n=read(),m=read(),B=n/A;
    for(int i=0;i<n;++i)a[i]=read();
    for(int i=n;i<(B+1)*A;++i)a[i]=i;
    for(int i=0;i<=B;++i){
        for(int j=i*A,k=0;k<A;++j,++k)rk0[i][k]=j;
        sort(rk0[i],rk0[i]+A,[](int x,int y){return a[x]<a[y];});
        for(int j=0;j<A;++j)rk1[rk0[i][j]]=j,cnt0[j][rk0[i][j]]=1;
        for(int j=i*A+1;j<(i+1)*A;++j)
            for(int k=0;k<A;++k)cnt0[k][j]+=cnt0[k][j-1];
        for(int j=i*A;j<(i+1)*A;++j)
            for(int k=1;k<A;++k)cnt0[k][j]+=cnt0[k-1][j];
        for(int j=i*A;j<(i+1)*A;++j)++cnt1[i][a[j]];
        if(i)for(int j=1;j<=101000;++j)cnt1[i][j]+=cnt1[i-1][j];
        for(int j=1,k=0;j<=101000;++j)(k<A)&&(j>=a[rk0[i][k]])&&(++k),lb[i][j]=k;
    }
    for(int i=0;i<=B;++i)
        for(int j=1;j<=101000;++j)cnt1[i][j]+=cnt1[i][j-1];
    for(int i=1;i<B;++i)for(int j=0;j<i;++j)for(int k=0;k<A;++k)
        cp0[i][j][k+1]=cnt1[j][a[rk0[i][k]]]+cp0[i][j][k];
    for(int i=0;i<B;++i)for(int j=0;j<A;++j)for(int k=j+1;k<A;++k)
        cp1[i][j][k]=cp1[i][j][k-1]+cnt0[k-1][rk0[i][k]]-((j==0)?0:cnt0[j-1][rk0[i][k]]);
    for(;m;--m){
        int l=read()-1,r=read()-1,x=read(),y=read(),bl=l/A,br=r/A;
        if(bl==br){
            int ans=0;
            for(int i=l;i<=r;++i){
                if(x<=a[i]&&a[i]<=y&&rk1[i])ans+=cnt0[rk1[i]-1][i]-((l%A)?cnt0[rk1[i]-1][l-1]:0);
                if(lb[bl][x-1]&&x<=a[i]&&a[i]<=y)ans-=cnt0[lb[bl][x-1]-1][i]-((l%A&&lb[bl][x-1])?cnt0[lb[bl][x-1]-1][l-1]:0);
            }
            pi(ans);
        }
        else{
            ll ans=0;
            for(int i=l;i<(bl+1)*A;++i){
                if(x<=a[i]&&a[i]<=y&&rk1[i])ans+=cnt0[rk1[i]-1][i]-((l%A)?cnt0[rk1[i]-1][l-1]:0);
                if(lb[bl][x-1]&&x<=a[i]&&a[i]<=y)ans-=cnt0[lb[bl][x-1]-1][i]-((l%A&&lb[bl][x-1])?cnt0[lb[bl][x-1]-1][l-1]:0);
                if(x<=a[i]&&a[i]<=y)ans+=cnt1[br-1][y]-cnt1[bl][y]-cnt1[br-1][a[i]]+cnt1[bl][a[i]];
            }
            for(int i=br*A;i<=r;++i){
                if(x<=a[i]&&a[i]<=y&&rk1[i])ans+=cnt0[rk1[i]-1][i];
                if(lb[br][x-1]&&x<=a[i]&&a[i]<=y)ans-=cnt0[lb[br][x-1]-1][i];
                if(x<=a[i]&&a[i]<=y)ans+=cnt1[br-1][a[i]]-cnt1[bl][a[i]]-cnt1[br-1][x-1]+cnt1[bl][x-1];
            }
            int lt=0,rt=0;
            for(int i=0;i<A;++i){
                if(rk0[bl][i]>=l&&x<=a[rk0[bl][i]]&&a[rk0[bl][i]]<=y)L[++lt]=rk0[bl][i];
                if(rk0[br][i]<=r&&x<=a[rk0[br][i]]&&a[rk0[br][i]]<=y)R[++rt]=rk0[br][i];
            }
            for(int i=1,t=1;i<=rt;++i){
                while(t<=lt&&a[L[t]]<a[R[i]])++t;
                ans+=t-1;
            }
            for(int i=bl+1;i<br;++i)if(lb[i][y])ans+=cp1[i][lb[i][x-1]][lb[i][y]-1];
            for(int i=bl+2;i<br;++i)
                ans+=cp0[i][i-1][lb[i][y]]-cp0[i][bl][lb[i][y]]-cp0[i][i-1][lb[i][x-1]]+cp0[i][bl][lb[i][x-1]],
                ans-=ll(cnt1[i][y]-cnt1[i-1][y]-cnt1[i][x-1]+cnt1[i-1][x-1])*(cnt1[i-1][x-1]-cnt1[bl][x-1]);
            pi(ans);
        }
    }
    return 0;
}

标签 data structures 下的文章

「codeforces - 1555F」Good Graph

Solution -「NOI 2021」轻重边

Description

Solution

Solution Set -「ARC 124」

「ARC 124A」LR Constraints

「ARC 124B」XOR Matching 2

「ARC 124C」LCM of GCDs

「ARC 124D」Yet Another Sorting Problem

「ARC 124E」Pass to Next

「ARC 124F」Chance Meeting

Solution -「营业」「CF 527C」Glass Carving

Description

Solution

Solution -「NOI 2020」时代的眼泪

Description

Solution