CFGym101138D Strange Queries 莫队/分块

时间：2021-02-23 11:49:08

正解:莫队/分块

解题报告:

传送门

ummm这题耗了我一天差不多然后我到现在还没做完:D

而同机房的大佬用了一个小时没有就切了?大概这就是大佬和弱鸡的差距趴QAQ

然后只是大概写下思想好了因为代码我还没打出来QAQ

先说莫队?

莫队似乎有俩方式能过呢

首先是个暴力,就只对l1r1排序让l2r2乱跳,然后神仙hl过去了?然后我就过不去?委屈:D

然后可以前缀和优化一波,这个大概是最稳的,然后文佬的博客似乎写了qwq有时间再研究下趴QAQ大概思路知道一下就成立就是个二维前缀和的玩意儿qwq

然后说分块

ummm分块这个还,挺神仙的qwq,我研究了下那个代码但还没有很清楚QAQ先把写了点儿注释的放上来QAQ

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
;
;

int n,m,tmp,q,B;
struct Block{ int a[N],b[M],c; }b[M];//b[i]:这个块内部第i个元素是啥 a[i]:包括这个块,data=i的数出现了几遍 c:这个块有多大
int bl[N],a[N],t1[N],t2[N],t3[N],t4[N];
LL f[M][M];

inline int in()
{
    ;;
    '))ch=getchar();
    ;
    )+(x<<)+(ch^'),ch=getchar();
    return y?x:-x;
}
]) ;else return bl[x]; }
]) ;else return bl[x]; }
LL work(int l1,int r1,int l2,int r2)
{
    ;
    ];
    //大端内部处理
    ,c2=;
    if(bl[l1] != bl[r1])
    {
        for(int i=l1;bl[i]<L1;i++) t1[++c1]=a[i],t2[a[i]]++;
        ;i<=r1;i++) t1[++c1]=a[i],t2[a[i]]++;
    }
    ]==bl[l1] || bl[r1]==bl[r1+]) for(int i=l1;i<=r1;i++) t1[++c1]=a[i],t2[a[i]]++;
    //朴素countl1r1的小端
    if(bl[l2]!=bl[r2])
    {
        for(int i=l2;bl[i]<L2;i++) t3[++c2]=a[i],t4[a[i]]++;
        ;i<=r2;i++) t3[++c2]=a[i],t4[a[i]]++;
    }
    ]==bl[l2] || bl[r2]==bl[r2+]) for(int i=l2;i<=r2;i++) t3[++c2]=a[i],t4[a[i]]++;
    //朴素countl2r2的小端
    ;i<=c1;i++) res+=(L2<=R2 ? b[R2].a[t1[i]]-b[L2-].a[t1[i]] : ) + t4[t1[i]];
    //朴素把l1r1小端的处理辽,用大端+小端
    ;i<=c2;i++) res+=b[R1].a[t3[i]]-b[L1-].a[t3[i]];
    //朴素处理小端
    ;i<=c1;i++) t2[t1[i]]--;
    ;i<=c2;i++) t4[t3[i]]--;
    //清零
    return res;
}
int main()
{
    n=,B=sqrt(n)+;
    ;i<=n;i++)
    {
        if(b[m].c >= B) ++m;
        a[i]=in(),bl[i]=m,b[m].b[++b[m].c]=a[i];
    }
    ;i<=m;i++)
    {
        ;j<=n;j++) b[i].a[j]=b[i-].a[j];
        ;j<=b[i].c;j++) b[i].a[b[i].b[j]]++;
    }
    ;i<=m;i++) ;j<=m;j++) ;k<=b[i].c;k++) f[i][j]+=b[j].a[b[i].b[k]];//第i个块到第j个块的ans
    for(q=in();q--;)
    {
        int l1=in(),r1=in(),l2=in(),r2=in();
        cout<<work(l1,r1,l2,r2)<<endl;
    };
}

这儿,是,代码QAQ

先这样不想刚这题了,over

相关文章