#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib>
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
//#define int long long
//#define double long double
const int mod=10007,mxn=1e5+5,lg=60,inf=1e9,minf=-1e9,Mxn=1e6+50000;
int n,m;
struct node{
int dp[22];
node operator+(node a)const{
node tmp;
for(int i=0;i<=m;i++)tmp.dp[i]=0;
for(int i=0;i<=m;i++)for(int j=0;j<=i;j++)tmp.dp[i]=(tmp.dp[i]+(a.dp[i-j]*dp[j])%mod)%mod;
return tmp;
}
void init(){
for(int i=0;i<=m;i++)dp[i]=0;
dp[0]=1;
}
void print(){
for(int i=0;i<=m;i++)cout<<dp[i]<<" ";
cout<<'\n';
}
};
struct seg{
node v[2*mxn+10];
void init(){for(int i=0;i<=2*n;i++)v[i].init();}
void update(int pos,int a,int b){
pos+=n;
v[pos].init();
v[pos].dp[0]=b;
v[pos].dp[1]=a;
for(int i=pos;i>0;i>>=1)v[i>>1]=v[i]+v[i^1];
}
//1 2 1 4
//1 2 1 4
int qry(int l=0,int r=n-1){
node ans;
ans.init();
for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
if(l&1)ans=(ans+v[l++]);
if(!(r&1))ans=(ans+v[r--]);
}
int sum=0;
for(int i=0;i<=m;i++)sum=(sum+ans.dp[i])%mod;
return sum;
}
}t;
int inverse(int a){
int ex=mod-2,ans=1;
while(ex){
if(ex&1)ans=(ans*a)%mod;
a=(a*a)%mod;
ex>>=1;
}
return ans;
}
int bro[mxn+10],bro2[mxn+10];
int32_t main(){
fastio
//matrix segtree?
cin>>n>>m;
int ans=1;
m--;
for(int i=0;i<n;i++)cin>>bro[i];
for(int i=0;i<n;i++){
cin>>bro2[i];
bro[i]%=mod;
bro2[i]%=mod;
t.update(i,bro[i],bro2[i]);
ans=(ans*(bro[i]+bro2[i]))%mod;
}
int q;cin>>q;
while(q--){
int x,a,b;cin>>x>>a>>b;
x--;
ans=(ans*inverse(bro[x]+bro2[x]))%mod;
a%=mod;
b%=mod;
bro[x]=a,bro2[x]=b;
ans=(ans*(bro[x]+bro2[x]))%mod;
t.update(x,a,b);
int ra=(ans-t.qry()+mod)%mod;
cout<<ra<<'\n';
}
return 0;
}
/*
1 2 3 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
19 ms |
2516 KB |
Output is correct |
| 4 |
Correct |
282 ms |
10324 KB |
Output is correct |
| 5 |
Correct |
1141 ms |
17616 KB |
Output is correct |
| 6 |
Correct |
1925 ms |
17740 KB |
Output is correct |
| 7 |
Correct |
717 ms |
12624 KB |
Output is correct |
| 8 |
Correct |
398 ms |
16976 KB |
Output is correct |
| 9 |
Correct |
640 ms |
14420 KB |
Output is correct |
| 10 |
Correct |
2636 ms |
14236 KB |
Output is correct |
