2019ICPC 徐州

(Updated: )
(7 mins to read)

F

暴力打表即可，不过在我电脑上跑的挺慢的。。

C

素数密度是不断变小的

A

利用连续整数异或和的trick即可，只要小范围枚举左右两端点，中间一大段大概率可以是0

E

求出$\frac{Y!} {\prod {a_i}}$​是X的多少次方的倍数利用pollardrho求解X的所有素因子，然后求出各个阶乘中各素因子幂次的数量，乘法+，除法-，最后每个素因子取个min，注意负数和正数上下取整的问题

H

单点修改，区间询问该段区间最小的不能被表示的数洛谷p4587+修改先考虑不带修改的情况，对[l,r]内的数从小到大考虑，假设当前能够表示出[1,cur]的范围，如果询问[1,cur+1]的值等于cur，说明剩余的值都是大于等于cur+2的，此时cur+1是无法被表示出来的，所以break，容易发现该操作中cur的增长速度是fibnacci级别的，利用主席树完成二维数点问题。至于修改，在外层套一个树状数组即可，复杂度$O(n \log^3 n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5, up = 2e5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, q, a[N];
namespace PSegTree
{
  #define ls(x) t[x].l
  #define rs(x) t[x].r
  int rt[N], tot;
  int lrt[N], rrt[N], lc, rc;
  struct node
  {
    int l, r;
    ll sum;
  }t[N*128];
  void insert(int &p, int l, int r, int x, int v)
  {
    if(!p) p = ++tot;
    t[p].sum += x*v;
    if(l==r) return;
    int mid = (l+r) >> 1;
    if(x<=mid) insert(ls(p), l, mid, x, v);
    else insert(rs(p), mid+1, r, x, v);
  }
  ll ask(int l, int r, int x)
  {
    if(l==r)
    {
      ll ans = 0;
      for(int i=1; i<=lc; i++) ans -= t[lrt[i]].sum;
      for(int i=1; i<=rc; i++) ans += t[rrt[i]].sum;
      return ans;
    }
    int mid = (l+r) >> 1;
    if(x<=mid)
    {
      for(int i=1; i<=lc; i++) lrt[i] = ls(lrt[i]);
      for(int i=1; i<=rc; i++) rrt[i] = ls(rrt[i]);
      return ask(l, mid, x);
    }
    else
    {
      ll ans = 0;
      for(int i=1; i<=lc; i++) ans -= t[ls(lrt[i])].sum;
      for(int i=1; i<=rc; i++) ans += t[ls(rrt[i])].sum;
      for(int i=1; i<=lc; i++) lrt[i] = rs(lrt[i]);
      for(int i=1; i<=rc; i++) rrt[i] = rs(rrt[i]);
      return ans + ask(mid+1, r, x);
    }
  }
  #undef ls
  #undef rs
}
using namespace PSegTree;
void upd(int x, int v)
{
  for(int i=x; i<=n; i+=(i&-i)) insert(rt[i], 1, up, a[x], v);
}
ll query(int l, int r, int x)
{
  lc = rc = 0;
  for(int i=l-1; i>0; i-=(i&-i)) lrt[++lc] = rt[i];
  for(int i=r; i>0; i-=(i&-i)) rrt[++rc] = rt[i];
  return ask(1, up, x);
}
int main()
{
  scanf("%d%d", &n, &q);
  for(int i=1; i<=n; i++) scanf("%d", a+i);
  for(int i=1; i<=n; i++) upd(i, 1);
  while(q--)
  {
    int op, x, y;
    scanf("%d%d%d", &op, &x, &y);
    if(op==1)
    {
      upd(x, -1);
      a[x] = y;
      upd(x, 1);
    }
    else
    {
      ll cur = 0;
      while(true)
      {
        ll sum = query(x, y, min((ll)up, cur+1));
        if(sum==cur) break;
        cur = sum;
      }
      printf("%lld\n", cur+1);
    }
  }
  return 0;
}