辽宁省住房和城乡建设厅网站进不去,网站建设黄页免费在线观看,网页版微信文件保存在哪里,门户网站域名正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP4168 题目大意
询问区间众数 解题思路
将数字离散化#xff0c;然后分块。对于数组vi,j,kv_{i,j,k}vi,j,k#xff0c;表示i∼ji\sim ji∼j个块#xff0c;kkk的个数。对于询问(l,r)(l,r)(l,r)52918pidP4168 题目大意
询问区间众数 解题思路
将数字离散化然后分块。对于数组vi,j,kv_{i,j,k}vi,j,k表示i∼ji\sim ji∼j个块kkk的个数。对于询问(l,r)(l,r)(l,r)将整块的直接累计然后局部的直接暴力。
时间复杂度:O(NT2MNT)O(NT^2\frac{MN}{T})O(NT2TMN)根据LYD的说法让T≈n3T\approx \sqrt[3]nT≈3n的话时间复杂度就可以在O(N53)O(N^{\frac{5}{3}})O(N35)级别。
代码写优美些或者加点优化就可以过。 code
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)
%:pragma GCC optimize(-fgcse)
%:pragma GCC optimize(-fgcse-lm)
%:pragma GCC optimize(-fipa-sra)
%:pragma GCC optimize(-ftree-pre)
%:pragma GCC optimize(-ftree-vrp)
%:pragma GCC optimize(-fpeephole2)
%:pragma GCC optimize(-ffast-math)
%:pragma GCC optimize(-fsched-spec)
%:pragma GCC optimize(unroll-loops)
%:pragma GCC optimize(-falign-jumps)
%:pragma GCC optimize(-falign-loops)
%:pragma GCC optimize(-falign-labels)
%:pragma GCC optimize(-fdevirtualize)
%:pragma GCC optimize(-fcaller-saves)
%:pragma GCC optimize(-fcrossjumping)
%:pragma GCC optimize(-fthread-jumps)
%:pragma GCC optimize(-funroll-loops)
%:pragma GCC optimize(-fwhole-program)
%:pragma GCC optimize(-freorder-blocks)
%:pragma GCC optimize(-fschedule-insns)
%:pragma GCC optimize(inline-functions)
%:pragma GCC optimize(-ftree-tail-merge)
%:pragma GCC optimize(-fschedule-insns2)
%:pragma GCC optimize(-fstrict-aliasing)
%:pragma GCC optimize(-fstrict-overflow)
%:pragma GCC optimize(-falign-functions)
%:pragma GCC optimize(-fcse-skip-blocks)
%:pragma GCC optimize(-fcse-follow-jumps)
%:pragma GCC optimize(-fsched-interblock)
%:pragma GCC optimize(-fpartial-inlining)
%:pragma GCC optimize(no-stack-protector)
%:pragma GCC optimize(-freorder-functions)
%:pragma GCC optimize(-findirect-inlining)
%:pragma GCC optimize(-fhoist-adjacent-loads)
%:pragma GCC optimize(-frerun-cse-after-loop)
%:pragma GCC optimize(inline-small-functions)
%:pragma GCC optimize(-finline-small-functions)
%:pragma GCC optimize(-ftree-switch-conversion)
%:pragma GCC optimize(-foptimize-sibling-calls)
%:pragma GCC optimize(-fexpensive-optimizations)
%:pragma GCC optimize(-funsafe-loop-optimizations)
%:pragma GCC optimize(inline-functions-called-once)
%:pragma GCC optimize(-fdelete-null-pointer-checks)
#includecstdio
#includecmath
#includealgorithm
#includecstring
#define Tn 40
#define N 40010
using namespace std;
int n,m,L[Tn],R[Tn],v[Tn][Tn][N],l,r,num[N];
int z[N],w[N],a[N],cnt,k[N],t,T,pos[N],x;
bool cmp(int x,int y)//排序
{return z[x]z[y];}
void begins()//预处理
{for(int i1;it;i){L[i](i-1)*T1;R[i]i*T;}if(R[t]n) t,L[t]R[t-1]1,R[t]n;//计算边界for(int i1;it;i)for(int ji;jt;j)for(int kL[i];kR[j];k)v[i][j][a[k]];//计算v数组
}
int ask(int l,int r)
{int ppos[l],qpos[r];if(p-q2){memset(k,0,sizeof(k));for(int il;ir;i)k[a[i]];}else{p;q--;for(int i1;icnt;i)k[i]v[p][q][i];//直接累计for(int il;iL[p];i)//暴力统计k[a[i]];for(int iR[q]1;ir;i)//暴力统计*2k[a[i]];}int mark1;for(int i2;icnt;i)//找众数if(k[i]k[mark]) marki;return w[mark];
}
int main()
{scanf(%d%d,n,m);t(int)pow(double(n),1.0/3);Tn/t;for(int i1;in;i){scanf(%d,z[i]);num[i]i;}sort(num1,num1n,cmp);z[0]-1;for(int i1;in;i)//离散化{if(z[num[i]]!z[num[i-1]]) cnt,w[cnt]z[num[i]];;a[num[i]]cnt;}Tn/t;begins();for(int i1;im;i){scanf(%d%d,l,r);l(lx-1)%n1;r(rx-1)%n1;if(lr) swap(l,r);printf(%d\n,xask(l,r));}
}
