正解:莫队/分块
解题报告:
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