diqiuyi @ 2022-05-15 21:33:56
T了第65个点，卡了常也没用。
#pragma GCC optimize (3)
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=0;bool f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f?x:-x;
}
inline int write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+48);
}
int a[500005],n,m,block,tim[500005],ans[500005],sum,stk[500005],top,ku[500005],pos[500005];
struct qu{
int l,r,id;
}q[500005];
inline void Add(int x){
tim[a[x]]++;
if(tim[a[x]]==1)
stk[++top]=a[x],pos[a[x]]=top;
else if(tim[a[x]]==2)
stk[pos[a[x]]]=stk[top],pos[stk[top]]=pos[a[x]],stk[top--]=pos[a[x]]=0;
}
inline void Del(int x){
tim[a[x]]--;
if(tim[a[x]]==1)
stk[++top]=a[x],pos[a[x]]=top;
else if(!tim[a[x]])
stk[pos[a[x]]]=stk[top],pos[stk[top]]=pos[a[x]],stk[top--]=pos[a[x]]=0;
}
inline bool cmp(qu x,qu y){
return (ku[x.l]^ku[y.l])?ku[x.l]<ku[y.l]:(ku[x.l]&1)?x.r<y.r:x.r>y.r;
}
int main(){
n=read(),block=sqrt(n);
for(int i=1;i<=n;i++)
a[i]=read(),ku[i]=(i-1)/block+1;
m=read();
for(int i=1;i<=m;i++)
q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1,q+m+1,cmp);
for(int lct=1,rct=0,i=1;i<=m;i++){
while(lct<q[i].l)
Del(lct++);
while(lct>q[i].l)
Add(--lct);
while(rct>q[i].r)
Del(rct--);
while(rct<q[i].r)
Add(++rct);
ans[q[i].id]=stk[top];
}
for(int i=1;i<=m;i++)
write(ans[i]),putchar(10);
return 0;
}by Cocoly1990 @ 2022-05-15 21:46:25
@diqiuyi 我卡过了
by Cocoly1990 @ 2022-05-15 21:47:00
@diqiuyi 157315717
by Cocoly1990 @ 2022-05-15 21:47:17
#pragma GCC optimize (3)
#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
namespace io {
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc (char &x) { x = Gc(); }
inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';) __c = Gc();
for(; __c > 31 && __c < 127 && __c != ' ' && __c != '\n' && __c != '\r'; ++s, __c = Gc()) *s = __c; *s = 0; }
template <class I> inline bool gi (I &x) { _eof = 0;
for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10; while (qr) pc (qu[qr --]); }
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;
using namespace std;
inline int read(){
int x=0;bool f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f?x:-x;
}
inline int write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+48);
}
int a[500005],n,m,block,tim[500005],ans[500005],sum,stk[500005],top,ku[500005],pos[500005];
struct qu{
int l,r,id;
}q[500005];
inline void Add(int x){
tim[a[x]]++;
if(tim[a[x]]==1)
stk[++top]=a[x],pos[a[x]]=top;
else if(tim[a[x]]==2)
stk[pos[a[x]]]=stk[top],pos[stk[top]]=pos[a[x]],stk[top--]=pos[a[x]]=0;
}
inline void Del(int x){
tim[a[x]]--;
if(tim[a[x]]==1)
stk[++top]=a[x],pos[a[x]]=top;
else if(!tim[a[x]])
stk[pos[a[x]]]=stk[top],pos[stk[top]]=pos[a[x]],stk[top--]=pos[a[x]]=0;
}
inline bool cmp(qu x,qu y){
return (ku[x.l]^ku[y.l])?ku[x.l]<ku[y.l]:(ku[x.l]&1)?x.r<y.r:x.r>y.r;
}
int main(){
n=read(),block=sqrt(n);
for(int i=1;i<=n;i++)
a[i]=read(),ku[i]=(i-1)/block+1;
m=read();
for(int i=1;i<=m;i++)
{gi(q[i].l); gi(q[i].r); q[i].id=i;}
sort(q+1,q+m+1,cmp);
for(int lct=1,rct=0,i=1;i<=m;i++){
while(lct<q[i].l)
Del(lct++);
while(lct>q[i].l)
Add(--lct);
while(rct>q[i].r)
Del(rct--);
while(rct<q[i].r)
Add(++rct);
ans[q[i].id]=stk[top];
}
for(int i=1;i<=m;i++)
write(ans[i]),putchar(10);
return 0;
}by diqiuyi @ 2022-05-15 21:51:02
@Cocoly1990 tql%%%
by Cocoly1990 @ 2022-05-15 21:56:33
@diqiuyi 没什么强的，还贺了您的代码。
by diqiuyi @ 2022-05-15 21:58:02
@Cocoly1990 没事我也贺了您的。
by diqiuyi @ 2022-05-15 21:58:57
不对啊我怎么又 T 了
by diqiuyi @ 2022-05-15 22:01:54
二次绝望
by Cocoly1990 @ 2022-05-15 22:04:00
@diqiuyi 不会啊我AC记录都给你了。
by Cocoly1990 @ 2022-05-15 22:05:02
@diqiuyi 你复制了我的快读，读入有没有改。