fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define mp make_pair
  7. #define REP(i, n) for (int i = 0; i < (int)(n); ++i)
  8. typedef long long LL;
  9. typedef pair<int, int> PII;
  10.  
  11. const int MOD = 10007;
  12.  
  13. int n, c, q;
  14. int a[100000], b[100000];
  15. int st[1 << 18][20], stot[1 << 18];
  16. const int off = 1 << 17;
  17.  
  18. void stMerge(int v, int l, int r) {
  19.     int *s = st[v];
  20.     int *a = st[l];
  21.     int *b = st[r];
  22.     REP(i, c) {
  23.         s[i] = 0;
  24.         REP(j, i + 1) s[i] += a[j] * b[i - j];
  25.         s[i] %= MOD;
  26.     }
  27.     stot[v] = stot[l] * stot[r] % MOD;
  28. }
  29.  
  30. void stBuild() {
  31.     REP(i, n) {
  32.         st[off + i][0] = b[i];
  33.         st[off + i][1] = a[i];
  34.         stot[off + i] = (a[i] + b[i]) % MOD;
  35.     }
  36.     for (int i = n; i < off; ++i) {
  37.         st[off + i][0] = 1;
  38.         stot[off + i] = 1;
  39.     }
  40.     for (int i = off - 1; i >= 1; --i) {
  41.         stMerge(i, i << 1, (i << 1) | 1);
  42.     }
  43. }
  44.  
  45. void stUpdate(int pos, int a, int b) {
  46.     pos += off;
  47.     st[pos][0] = b;
  48.     st[pos][1] = a;
  49.     stot[pos] = a + b;
  50.     if (stot[pos] >= MOD) stot[pos] -= MOD;
  51.     for (pos >>= 1; pos >= 1; pos >>= 1) {
  52.         stMerge(pos, pos << 1, (pos << 1) | 1);
  53.     }
  54. }
  55.  
  56. int main() {
  57.     scanf("%d%d", &n, &c);
  58.     REP(i, n) scanf("%d", a + i), a[i] %= MOD;
  59.     REP(i, n) scanf("%d", b + i), b[i] %= MOD;
  60.     stBuild();
  61.     scanf("%d", &q);
  62.     REP(query, q) {
  63.         int x, y, z;
  64.         scanf("%d%d%d", &x, &y, &z), --x, y %= MOD, z %= MOD;
  65.         stUpdate(x, y, z);
  66.         int ans = stot[1];
  67.         REP(i, c) ans -= st[1][i];
  68.         ans %= MOD;
  69.         if (ans < 0) ans += MOD;
  70.         printf("%d\n", ans);
  71.     }
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0.02s 25704KB
comments (?)
stdin
copy 
4 2
1 2 3 4
1 2 3 4
1
4 1 1
stdout
copy 
66
https://ideone.com/nd4dDL
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!