NC204649. 久岛 鸥
描述
「你要去哪里」
鸥「……」
「我记得，你的本体，现在应该是在外国对吧」
「你是要回那里去吗」
鸥「……」
鸥「不是的」
鸥慢慢地摇了摇头。 然后，望向了天空。望向了，那闪耀着无数繁星的，那无比遥远的天空。鸥「是一个更加——」
鸥「遥远的地方」
「更加遥远的地方……？」
输入描述
第一行三个正整数 n,m 和 type，分别表示星星序列长度、询问次数和强制在线参数。
接下来一行 n 个正整数，其中第 i 个正整数表示序列中的第 i 个数 ai。接下来 m 行，每行三个整数 l,r 和 k，表示一次询问。若强制在线参数 type=1 则实际询问的 l',r' 和 k' 由输入的 l,r 和 k 经以下运算得到：l' = l xor lastansr' = r xor lastansk' = k xor lastans其中 xor 为按位异或运算，lastans 为上次询问的答案，初始时 lastans=0。
输出描述
共 m 行，每行输出一个整数表示你的答案。
示例1
输入:
10 10 1 2 3 1 1 4 4 1 2 1 4 8 10 2 4 8 0 7 8 3 11 11 2 3 7 0 0 0 0 5 5 1 4 7 0 3 1 3 3 11 0
输出:
1 2 3 1 2 0 1 2 1 4
说明:
C++14(g++5.4) 解法, 执行用时: 2292ms, 内存消耗: 200552K, 提交时间: 2020-04-30 07:26:07
#include<bits/stdc++.h>
using namespace std;
const int block=316,si=304,N=1e5+100;
int n,m,t,q,s[N],L[N],R[N],res[305],sum[N][345],a[N],type,vis[345][345][305];
vector<int>v,f[N];
bool vv[N];
void add(int x)
{
if(a[x]==0) return;
res[s[a[x]]]--;
s[a[x]]++;
res[s[a[x]]]++;
}
int get(int l,int r,int x)
{
return upper_bound(f[x].begin(),f[x].end(),r)-upper_bound(f[x].begin(),f[x].end(),l-1);
}
int main()
{
scanf("%d%d%d",&n,&t,&type);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),s[a[i]]++;
for(int i=1;i<=n;i++)
if(s[i]>si) v.push_back(i);
for(int i=0;i<v.size();i++)
for(int j=1;j<=n;j++)
{
sum[j][i]=sum[j-1][i]+(a[j]==v[i]);
if(a[j]==v[i]) a[j]=0;
}
memset(s,0,sizeof(s));
m=n/block;
for(int i=1;i<=m;i++) L[i]=n;
for(int i=1;i<=n;i++) L[i/block]=min(L[i/block],i),R[i/block]=max(R[i/block],i);
for(int i=1;i<=m;i++)
{
memset(s,0,sizeof(s));
memset(res,0,sizeof(res));
for(int j=i;j<=m;j++)
{
for(int k=L[j];k<=R[j];k++) add(k);
memcpy(vis[i][j],res,sizeof(res));
}
}
for(int i=1;i<=n;i++)
if(a[i]) f[a[i]].push_back(i);
int lastans=0;
while(t--)
{
int l,r,k;scanf("%d%d%d",&l,&r,&k);
if(type==1) l^=lastans,r^=lastans,k^=lastans;
int le=l/block,ri=r/block;
if(l!=L[le]) le++;
if(r!=R[ri]) ri--;
vector<int>b;
if(le>ri)
{
memset(res,0,sizeof res);
for(int i=l;i<=r;i++)
if(a[i]&&!vv[a[i]])
b.push_back(a[i]),vv[a[i]]=true;
}
else
{
memcpy(res,vis[le][ri],sizeof(res));
for(int i=l;i<L[le];i++)
if(a[i]&&!vv[a[i]])
b.push_back(a[i]),vv[a[i]]=true;
for(int i=R[ri]+1;i<=r;i++)
if(a[i]&&!vv[a[i]])
b.push_back(a[i]),vv[a[i]]=true;
}
for(int x:b)
{
vv[x]=false;
if(le<=ri)
res[get(L[le],R[ri],x)]--;
res[get(l,r,x)]++;
}
vector<int>vc;
for(int i=0;i<v.size();i++)
{
if(sum[r][i]-sum[l-1][i]<=si) res[sum[r][i]-sum[l-1][i]]++;
else vc.push_back(sum[r][i]-sum[l-1][i]);
}
if(k<=vc.size())
{
sort(vc.begin(),vc.end(),greater<int>());
printf("%d\n",lastans=vc[k-1]);
}
else
{
k-=vc.size();
lastans=0;
for(int i=si;i>=1;i--)
{
k-=res[i];
if(k<=0)
{
lastans=i;break;
}
}
printf("%d\n",lastans);
}
}
}
C++(clang++11) 解法, 执行用时: 4856ms, 内存消耗: 520336K, 提交时间: 2021-04-18 11:24:22
#include<bits/stdc++.h>
#define REPI(n) for(int i=0;i<(n);++i)
#define REPJ(n) for(int j=0;j<(n);++j)
#define FOR(v,s,e) for(int (v)=(s);(v)<(e);++(v))
#define MSET(v,a) memset(a,v,sizeof(a))
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)<(b)?(a):(b)
typedef long long ll;
using namespace std;
int readtmp;
inline int read(int& v = readtmp) {
scanf("%d", &v);
return v;
}
const int maxn = 1e5 + 7;
const int maxl = 660;
int n, m, type;
int l, r, k;
int a[maxn];
int cnt[maxl][maxn];
int cct[maxl][maxn];
int smpl[maxl];
int smpr[maxl];
int smpnum = 0;
int ln, rn;
int *cntn, *cctn;
inline void addStar(int star) {
cctn[cntn[star]]--;
cctn[++cntn[star]]++;
}
inline void rmvStar(int star) {
cctn[cntn[star]]--;
cctn[--cntn[star]]++;
}
inline void move(int l, int r) {
while (rn < r) addStar(a[++rn]);
while (ln > l) addStar(a[--ln]);
while (rn > r) rmvStar(a[rn--]);
while (ln < l) rmvStar(a[ln++]);
}
void setsmp(int l, int r) {
ln = 1;
rn = 0;
cntn = cnt[smpnum];
cctn = cct[smpnum];
cctn[0] = maxn;
move(l, r);
smpl[smpnum] = l;
smpr[smpnum] = r;
smpnum++;
}
void usesmp(int l, int r,int index) {
cntn = cnt[index];
cctn = cct[index];
ln = smpl[index];
rn = smpr[index];
move(l, r);
smpl[index] = ln;
smpr[index] = rn;
}
int main()
{
MSET(0, cnt);
MSET(0, cct);
read(n);
read(m);
read(type);
REPI(n) read(a[i + 1]);
ln = 1;
rn = 0;
cntn = cnt[0];
cctn = cct[0];
int lastans = 0;
REPI(m) {
read(l);
read(r);
read(k);
if (type == 1) {
l ^= lastans;
r ^= lastans;
k ^= lastans;
}
int cost = r - l + 1;
if (smpnum == maxl) cost = INT_MAX;
int index = -1;
REPI(smpnum) {
int ncost = abs(smpl[i] - l) + abs(smpr[i] - r);
if (ncost < cost) {
cost = ncost;
index = i;
}
}
if (index == -1) {
setsmp(l, r);
}
else {
usesmp(l, r, index);
}
int sum = r - l + 1;
int now = 0;
while (sum > 0) {
now++;
sum -= cctn[now] * now;
}
while (now > 0) {
k -= cctn[now];
if (k <= 0) break;
now--;
}
lastans = now;
printf("%d\n", lastans);
}
}