#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e15
#define N 5000
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;
int d[N+5][N+5],mx[N+5],mp[N+5];
multiset<int> ms;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int n,k,q;
cin >> n >> k >> q;
int a[n+1],b[n+1];
for(int i=1;i<=n;i++)
cin >> a[i];
for(int i=1;i<=n;i++)
cin >> b[i];
for(int i=1;i<=n-k+1;i++){
if(i==1){
for(int it=1;it<=k;it++)
mp[a[it]]++;
}
else mp[a[i-1]]--,mp[a[i+k-1]]++;
int t=0;
for(int j=1;j<=n-k+1;j++){
if(j==1){
for(int it=1;it<=k;it++)
t+=mp[b[it]];
}
else t+=mp[b[j+k-1]]-mp[b[j-1]];
d[i][t]++;
mx[i]=max(mx[i],t);
}
ms.insert(mx[i]);
}
int ans=0,Max=*(--ms.end());
for(int i=1;i<=n-k+1;i++)
ans+=d[i][Max];
cout << Max sp ans << endl;
while(q--){
int x;
cin >> x;
swap(a[x],a[x+1]);
if(x>=k){
int i=x-k+1;
for(int it=1;it<=n;it++)
mp[it]=0;
ms.erase(ms.find(mx[i]));
mx[i]=0;
for(int it=1;it<=k;it++)
d[i][it]=0;
for(int it=i;it<=i+k-1;it++)
mp[a[it]]++;
int t=0;
for(int j=1;j<=n-k+1;j++){
if(j==1){
for(int it=1;it<=k;it++)
t+=mp[b[it]];
}
else t+=mp[b[j+k-1]]-mp[b[j-1]];
d[i][t]++;
mx[i]=max(mx[i],t);
}
ms.insert(mx[i]);
}
if(x+1<=n-k+1){
int i=x+1;
for(int it=1;it<=n;it++)
mp[it]=0;
ms.erase(ms.find(mx[i]));
mx[i]=0;
for(int it=1;it<=k;it++)
d[i][it]=0;
for(int it=i;it<=i+k-1;it++)
mp[a[it]]++;
int t=0;
for(int j=1;j<=n-k+1;j++){
if(j==1){
for(int it=1;it<=k;it++)
t+=mp[b[it]];
}
else t+=mp[b[j+k-1]]-mp[b[j-1]];
d[i][t]++;
mx[i]=max(mx[i],t);
}
ms.insert(mx[i]);
}
//~ for(int i=1;i<=n-k+1;i++){
//~ for(int j=1;j<=k;j++)
//~ cout << d[i][j] << " ";
//~ cout << endl;
//~ }
ans=0;Max=*(--ms.end());
for(int i=1;i<=n-k+1;i++)
ans+=d[i][Max];
cout << Max sp ans << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |