#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using ll=long long;
using pll=array<ll,2>;
const ll inf=1e18;
const int N=1e5+5,M=1e8+5;
pll mrg(pll L,pll R){
if(L[0]<R[0]) swap(L,R);
if(L[0]==R[0]) return {L[0],L[1]+R[1]};
return L;
}
struct node{
pll v={0,0}; int d=0;
int l=0,r=0;
}T[M]; int C=1;
void init(int nd,int l,int r){
T[nd].v={0,r-l+1};
T[nd].d=0;
if(l==r) return;
int m=(l+r)>>1;
T[nd].l=++C;
T[nd].r=++C;
init(T[nd].l,l,m); init(T[nd].r,m+1,r);
}
void upd(int n1,int n2,int l,int r,int s,int e,int v){
T[n2]=T[n1];
if(r<s||e<l) return;
if(s<=l&&r<=e){
T[n2].v[0]+=v;
T[n2].d+=v;
return;
}
int m=(l+r)>>1;
T[n2].l=++C;
T[n2].r=++C;
upd(T[n1].l,T[n2].l,l,m,s,e,v); upd(T[n1].r,T[n2].r,m+1,r,s,e,v);
T[n2].v=mrg(T[T[n2].l].v,T[T[n2].r].v);
T[n2].v[0]+=T[n2].d;
}
int n,k,q,a[N],b[N],invb[N],t[N];
int root[N];
map<int,ll> mp;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>k>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
cin>>b[i];
invb[b[i]]=i;
}
root[0]=1;
init(1,1,n-k+1);
for(int x=1;x<=n-k+1;x++){
root[x]=++C;
T[root[x]]=T[root[x-1]];
if(x==1){
for(int i=1;i<=k;i++){
int j=invb[a[i]];
int nroot=++C;
upd(root[x],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),1);
root[x]=nroot;
}
} else{
int j=invb[a[x+k-1]];
int nroot=++C;
upd(root[x],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),1);
root[x]=nroot;
{
int j=invb[a[x-1]];
int nroot=++C;
upd(root[x],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),-1);
root[x]=nroot;
}
}
mp[T[root[x]].v[0]]+=T[root[x]].v[1];
}
{
pair<int,ll> ans=*mp.rbegin();
cout<<ans.first<<" "<<ans.second<<"\n";
}
for(int i=1;i<=q;i++){
cin>>t[i];
if(k<=t[i]){
mp[T[root[t[i]-k+1]].v[0]]-=T[root[t[i]-k+1]].v[1];
int nroot=++C,j=invb[a[t[i]]];
upd(root[t[i]-k+1],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),-1);
root[t[i]-k+1]=nroot;
nroot=++C; j=invb[a[t[i]+1]];
upd(root[t[i]-k+1],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),1);
root[t[i]-k+1]=nroot;
mp[T[root[t[i]-k+1]].v[0]]+=T[root[t[i]-k+1]].v[1];
}
if(t[i]<=n-k){
mp[T[root[t[i]+1]].v[0]]-=T[root[t[i]+1]].v[1];
int nroot=++C,j=invb[a[t[i]]];
upd(root[t[i]+1],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),1);
root[t[i]+1]=nroot;
nroot=++C; j=invb[a[t[i]+1]];
upd(root[t[i]+1],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),-1);
root[t[i]+1]=nroot;
mp[T[root[t[i]+1]].v[0]]+=T[root[t[i]+1]].v[1];
}
swap(a[t[i]],a[t[i]+1]);
{
pair<int,ll> ans=*mp.rbegin();
while(ans.second==0){
mp.erase(ans.first);
ans=*mp.rbegin();
}
cout<<ans.first<<" "<<ans.second<<"\n";
}
}
return 0;
}
Compilation message
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
