做英雄联盟网站的图片素材,网站怎么做图片动态图,wordpress带会员主题,快速搭建网站模板 下载这道题算是好好写了。写了三种方法。 有一个好像是$qwq$$N\sqrt(N)$的方法#xff0c;#xff0c;但是恳请大佬们帮我看看为什么这么慢$qwq$#xff08;后面的第三种#xff09; 注:$pos[i]$表示$i$属于第$pos[i]$块。 第一种是统计所有可能的块组成的区间中#xff08;第…这道题算是好好写了。写了三种方法。 有一个好像是$qwq$$N\sqrt(N)$的方法但是恳请大佬们帮我看看为什么这么慢$qwq$后面的第三种 注:$pos[i]$表示$i$属于第$pos[i]$块。 第一种是统计所有可能的块组成的区间中第i块到第j块,每个数出现的次数记做$f[i][j][k]$和所有可能的块组成的区间的答案记做$h[i][j]$。 然后每次先把整块的答案作为初始答案然后对于散块中的每个值$vl$暴力修改对应的$f[i][j][vl]$,更新答案。 当块长取$N^\frac{2}{3}$,时间复杂度$O(N^\frac{5}{3})$级。 #includecstdio
#includeiostream
#includealgorithm
#includecstring
#includecmath
#includecctype
#includecstdlib
#includevector
#includequeue
#includemap
#includeset
#define ull unsigned long long
#define ll long long
#define R register int
#define pause (for(R i1;i10000000000;i))
#define OUT freopen(out.out,w,stdout);
using namespace std;
namespace Fread {static char B[115],*SB,*DB;#define getchar() (SD(D(SB)fread(B,1,115,stdin),SD)?EOF:*S)inline int g() {R ret0,fix1; register char ch; while(!isdigit(chgetchar())) fixch-?-1:fix;do retret*10(ch^48); while(isdigit(chgetchar())); return ret*fix;} inline bool isempty(const char ch) {return ch36||ch127;}inline void gs(char* s) {register char ch; while(isempty(chgetchar())); do *sch; while(!isempty(chgetchar()));}
}using Fread::g; using Fread::gs;
const int N40010,M37; int n,m,tot,T,lst;
int f[M][M][N],h[M][M],vl[N],a[N],b[N],pos[N];
inline void PRE() { R mx0,ans0;for(R i1;in;i) pos[i](i-1)/T1;for(R j1,Lpos[n];jL;j,mx0,ans0) for(R tj;tL;t) {memcpy(f[j][t],f[j][t-1],sizeof(f[j][t-1]));for(R i(t-1)*T1,LLmin(t*T,n);iLL;i) f[j][t][a[i]];for(R itot;i;--i) if(f[j][t][i]mx) mxf[j][t][i],ansi;h[j][t]ans;}
}
signed main() {
#ifdef JACKfreopen(NOIPAK.in,r,stdin);OUT;
#endifng(),mg(),Tn/pow(n,1.0/3);for(R i1;in;i) a[i]g(); memcpy(b,a,sizeof(a));sort(b1,bn1); totunique(b1,bn1)-b-1;for(R i1;in;i) a[i]lower_bound(b1,btot1,a[i])-b;memcpy(vl,b,sizeof(int)*(tot1)); PRE();for(R i1,l,r;im;i) { R mx0,ans0;l(g()lst-1)%n1,r(g()lst-1)%n1; lr?swap(l,r):(void)0;R ppos[l]1,qpos[r]-1; ansh[p][q],mxf[p][q][ans];if(pos[l]pos[r]) { for(R il;ir;i) { f[p][q][a[i]];if(f[p][q][a[i]]mx||(f[p][q][a[i]]mxa[i]ans)) mxf[p][q][a[i]],ansa[i];} for(R il;ir;i) --f[p][q][a[i]];} else { ansh[p][q],mxf[p][q][ans];for(R il,Lpos[l]*T;iL;i) { f[p][q][a[i]];if(f[p][q][a[i]]mx||(f[p][q][a[i]]mxa[i]ans)) mxf[p][q][a[i]],ansa[i];} for(R i(pos[r]-1)*T1;ir;i) { f[p][q][a[i]];if(f[p][q][a[i]]mx||(f[p][q][a[i]]mxa[i]ans)) mxf[p][q][a[i]],ansa[i];} for(R il,Lpos[l]*T;iL;i) --f[p][q][a[i]];for(R i(pos[r]-1)*T1;ir;i) --f[p][q][a[i]];} printf(%d\n,lstvl[ans]); }
} 第二种是预处理出所有可能的块组成的区间中第$i$块到第$j$块的答案$f[i][j]$,并且拿一个$vector$存每个数$vl$出现的位置$s[vl][1...n]$。 答案初始化为整块的答案然后对于散块中的每个数$vl$,在$s[vl]$中二分出$[l,r]$的最小和最大的位置的下标相减就是$[l,r]$有多少个$vl$,然后更新答案。 当块长取$\sqrt{\frac{N}{logN}}$,时间复杂度$O(N\sqrt{NlogN})$。 #includecstdio
#includeiostream
#includealgorithm
#includecstring
#includecmath
#includecctype
#includecstdlib
#includevector
#includequeue
#includemap
#includeset
#define ull unsigned long long
#define ll long long
#define R register int
#define pause (for(R i1;i10000000000;i))
#define OUT freopen(out.out,w,stdout);
using namespace std;
namespace Fread {static char B[115],*SB,*DB;#define getchar() (SD(D(SB)fread(B,1,115,stdin),SD)?EOF:*S)inline int g() {R ret0,fix1; register char ch; while(!isdigit(chgetchar())) fixch-?-1:fix;do retret*10(ch^48); while(isdigit(chgetchar())); return ret*fix;} inline bool isempty(const char ch) {return ch36||ch127;}inline void gs(char* s) {register char ch; while(isempty(chgetchar())); do *sch; while(!isempty(chgetchar()));}
}using Fread::g; using Fread::gs;
mapint,int mp;
const int N40010; int n,m,T,tot,lst;
vectorint s[N];
#define pb push_back
int f[10010][10010],cnt[N],p[N],pos[N],a[N],b[N],vl[N];
inline void PRE(int p) { R ans0,mx0; memset(cnt,0,sizeof(cnt)); for(R tp,limpos[n];tlim;t) {for(R i(t-1)*T1,limmin(n,t*T);ilim;i) {if(cnt[a[i]]mx||(cnt[a[i]]mxa[i]ans)) mxcnt[a[i]],ansa[i];} f[p][t]ans;}
}
inline int calc(int l,int r,int x) {return upper_bound(s[x].begin(),s[x].end(),r)-lower_bound(s[x].begin(),s[x].end(),l);}
inline int solve(int l,int r) { R mx0,ret0; if(pos[l]pos[r]) { memset(cnt,0,sizeof(cnt)); for(R il;ir;i) if(cnt[a[i]]mx||(cnt[a[i]]mxa[i]ret)) reta[i],mxcnt[a[i]];} else { retf[pos[l]1][pos[r]-1],mxcalc(l,r,ret);for(R il,limpos[l]*T;ilim;i) { R tcalc(l,r,a[i]);if(tmx||(tmxa[i]ret)) reta[i],mxt;} for(R i(pos[r]-1)*T1;ir;i) { R tcalc(l,r,a[i]);if(tmx||(tmxa[i]ret)) reta[i],mxt;}} return ret;
}
signed main() {
#ifdef JACKfreopen(NOIPAK.in,r,stdin);OUT;
#endifng(),mg();//,Tn/sqrt(n*log2(n));Tqpow(n,1.0/4);for(R i1;in;i) a[i]g();memcpy(b,a,sizeof(a)); sort(b1,bn1);totunique(b1,bn1)-b-1; memcpy(vl,b,sizeof(int)*(tot1));for(R i1;in;i) a[i]lower_bound(b1,btot1,a[i])-b,s[a[i]].pb(i);for(R i1;in;i) pos[i](i-1)/T1;for(R i1;ipos[n];i) PRE(i);for(R i1,l,r;im;i) {l(g()lst-1)%n1,r(g()lst-1)%n1; lr?swap(l,r):(void)0;printf(%d\n,lstvl[solve(l,r)]);}
} 第三种按理说是复杂度最优秀的但是跑的不是很快$qwq$。 同第二种预处理出所有可能的块组成的区间中第i块到第j块的答案$f[i][j]$,并且拿一个$vector$存每个数$vl$出现的位置$s[vl][1...n]$。 然后预处理$a[i]$是整个数列中的第几个$a[i]$,出第$1$到第$i$块中最靠后的$vl$是第几个$vl$记为$d[i][vl]$预处理出第$n$块到第$i$块中最靠前的$vl$是第几个$vl$,记为$h[i][vl]$。 对于左边散块中的$vl$查一下$d[pos[r]-1][vl]$,和右边散块中是否有更靠后的$vl$(可以事先用一个数组存起来)然后可以求出这个区间有多少个$vl$(每一个$vl$是第几个$vl$已经知道了),更新答案。 当块长取$\sqrt{n}$时时间复杂度为O(N\sqrt{N})级(不知道推没推错)。 #includecstdio
#includeiostream
#includealgorithm
#includecstring
#includecmath
#includecctype
#includecstdlib
#includevector
#includequeue
#includemap
#includeset
#define ull unsigned long long
#define ll long long
#define R register int
#define pause (for(R i1;i10000000000;i))
#define OUT freopen(out.out,w,stdout);
using namespace std;
namespace Fread {static char B[115],*SB,*DB;#define getchar() (SD(D(SB)fread(B,1,115,stdin),SD)?EOF:*S)inline int g() {R ret0,fix1; register char ch; while(!isdigit(chgetchar())) fixch-?-1:fix;do retret*10(ch^48); while(isdigit(chgetchar())); return ret*fix;} inline bool isempty(const char ch) {return ch36||ch127;}inline void gs(char* s) {register char ch; while(isempty(chgetchar())); do *sch; while(!isempty(chgetchar()));}
}using Fread::g; using Fread::gs;
const int N40010,M1000; int n,m,T,tot,lst;
vectorint s[N];
#define pb push_back
int f[M][M],cnt[N],P[N],pos[N],a[N],b[N],vl[N],h[M][N],d[M][N],c[M][M];
inline void PRE(int p) { R ans0,mx0; memset(cnt,0,sizeof(cnt)); for(R tp,limpos[n];tlim;t) {for(R i(t-1)*T1,limmin(n,t*T);ilim;i) {if(cnt[a[i]]mx||(cnt[a[i]]mxa[i]ans)) mxcnt[a[i]],ansa[i];} f[p][t]ans,c[p][t]mx;}
}
inline int solve(int l,int r) { R mx0,ret0,ppos[l]1,qpos[r]-1; if(pos[l]pos[r]) { memset(cnt,0,sizeof(cnt)); for(R il;ir;i) if(cnt[a[i]]mx||(cnt[a[i]]mxa[i]ret)) reta[i],mxcnt[a[i]];} else { retf[p][q],mxc[p][q]; memset(cnt,0x3f,sizeof(cnt));for(R il,Lpos[l]*T;iL;i) if(cnt[a[i]]0x3f3f3f3f) cnt[a[i]]P[i];for(R iq*T1;ir;i) {R tmpP[i]1-min(cnt[a[i]],h[p][a[i]]);if(tmpmx||(tmpmxa[i]ret)) reta[i],mxtmp;cnt[a[i]]P[i];} for(R il,Lpos[l]*T;iL;i) {R tmpmax((cnt[a[i]]0x3f3f3f3f?0:cnt[a[i]]),d[q][a[i]])-P[i]1;if(tmpmx||(tmpmxa[i]ret)) reta[i],mxtmp;} } return ret;
}
signed main() {
#ifdef JACKfreopen(NOIPAK.in,r,stdin);OUT;
#endifng(),mg(); Tpow(n,1/2.3);//好像更小一点更快也不是越小越快for(R i1;in;i) a[i]g();memcpy(b,a,sizeof(a)); sort(b1,bn1);totunique(b1,bn1)-b-1; memcpy(vl,b,sizeof(int)*(tot1));for(R i1;in;i) a[i]lower_bound(b1,btot1,a[i])-b,s[a[i]].pb(i);for(R i1;in;i) pos[i](i-1)/T1; for(R i1;in;i) P[i]cnt[a[i]]; memset(cnt,0,sizeof(cnt)); memset(h[pos[n]1],0x3f,sizeof(h[pos[n]1]));for(R tpos[n];t;--t) { memcpy(h[t],h[t1],sizeof(h[t1]));for(R imin(n,t*T);i(t-1)*T;--i) h[t][a[i]]P[i];} for(R t1;tpos[n];t) { memcpy(d[t],d[t-1],sizeof(d[t-1]));for(R i(t-1)*T1,Lt*T;iL;i) d[t][a[i]]P[i];} for(R i1;ipos[n];i) PRE(i); for(R i1,l,r;im;i) {l(g()lst-1)%n1,r(g()lst-1)%n1; lr?swap(l,r):(void)0;printf(%d\n,lstvl[solve(l,r)]);}
} 2019.06.28 转载于:https://www.cnblogs.com/Jackpei/p/11105253.html
