#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF (long long) 1e18//1234567890987654321
#define INF 1234567890
#define pb push_back
#define ins insert
#define f first
#define s second
#define db 0
#define EPS (1e-7) //0.0000001 the value
#define PI (acos(-1))
#define MAXN 300006
#define MAXK 26
#define MAXX 15000006
#define ll /*long long*/ int
#define ld long double
#define rep0(kk, l1, l2)for(ll kk = l1; kk < l2; kk++)
#define rep1(kk, l1, l2)for(ll kk = l1; kk <= l2; kk++)
#define foritr(itr, A) for(set<ll>::iterator itr = A.begin(); itr != A.end(); itr++)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ii++)
#define cr(x) cerr << #x << " = " << x << "\n";
#define crA(x, A) cerr << #x << " = " << A[x] << "\n";
#define spacing if(db)cout << " ";
#define space " "
#define cbr cout << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)));
#define bg(ms) (*ms.begin())
#define ed(ms) (*prev(ms.end(), 1))
#define addedge(a, b, c, v) v[(a)].pb(pi((b), (c))); v[(b)].pb(pi((a), (c)))
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n, c, A[MAXN/3], B[MAXN/3], q, C;
const long long MOD = (ll)10007;
struct node{
int s,e,m; short c;
//ll s, e, m, v, dpdp[25-23],c,I;
int dp[25];
node *l, *r;
node(ll _s, ll _e)
{
s = _s, e = _e, m = (s+e)/2; c = min(e-s+1,C);
//v = 0; I = 0;
mmst(dp,0);
if(s!=e)
{
l = new node(s,m);
r = new node(m+1,e);
}
if(s==e)
{
dp[0] = (B[s])%MOD;
dp[1] = A[s]%MOD;
return;
}
FOR(i,0,c)
{
dp[i] = 0;
for(ll j = 0; j <= i; j++)
{
dp[i] += ((l->dp[j]%MOD * r->dp[i-j]%MOD)%MOD);
dp[i]%=MOD;
}
}
for(ll i = 0; i <= c; i++)
{
for(ll j = c-i; j <= c; j++)
{
dp[c] += ((l->dp[i]%MOD * r->dp[j]%MOD)%MOD);
dp[c] %= MOD;
}
}
return;
}
void update(ll x)
{
if(s==e)
{
dp[0] = (B[s])%MOD;
dp[1] = A[s]%MOD;
return;
}
if(x>m) r->update(x);
else l->update(x);
mmst(dp,0);
FOR(i,0,c)
{
dp[i] = 0;
for(ll j = 0; j <= i; j++)
{
dp[i] += ((l->dp[j]%MOD * r->dp[i-j]%MOD)%MOD);
dp[i]%=MOD;
}
}
for(ll i = 0; i <= c; i++)
{
for(ll j = c-i; j <= c; j++)
{
dp[c] += ((l->dp[i]%MOD * r->dp[j]%MOD)%MOD);
dp[c] %= MOD;
}
}
//assert(l->dp[c+1] == 0);
//assert(r->dp[c+1] == 0);
// FOR(i,0,c+1)
// {
// FOR(j,0,c+1) if(i+j > c) I += ((l->dp[i] * r->dp[j])%MOD);
// }
return;
}
ll sz()
{
return e-s+1;
}
void trace()
{
if(s==e) { cout << s << ": " << dp[0] << ' ' << dp[1] << '\n'; return; }
l->trace();
r->trace();
cout << s << ' ' << m << ' ' << e << ' ' << dp[0] << ' ' << dp[1] << ' ' << dp[2] << ' ' << dp[3] << '\n';
}
} *seg;
int main()
{
FAST
cin >> n >> c; C=c;
FOR(i,0,n) cin >> A[i];
FOR(i,0,n) cin >> B[i];
seg = new node(0, n-1);
cin >> q;
FOR(ii,0,q)
{
ll x, a, b;
cin >> x >> a >> b; --x;
A[x]=a,B[x]=b;
seg->update(x);
cout << seg->dp[c] << "\n";
// seg->trace();
}
}
/*
4 2
1 2 3 4
1 2 3 4
1
4 1 1
* */
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
636 KB |
Output is correct |
| 2 |
Correct |
13 ms |
632 KB |
Output is correct |
| 3 |
Correct |
21 ms |
632 KB |
Output is correct |
| 4 |
Correct |
534 ms |
15996 KB |
Output is correct |
| 5 |
Correct |
1546 ms |
29448 KB |
Output is correct |
| 6 |
Correct |
2126 ms |
30624 KB |
Output is correct |
| 7 |
Correct |
1076 ms |
18984 KB |
Output is correct |
| 8 |
Correct |
642 ms |
30072 KB |
Output is correct |
| 9 |
Correct |
1114 ms |
26016 KB |
Output is correct |
| 10 |
Correct |
3462 ms |
24928 KB |
Output is correct |
