洛谷7月月赛

(Updated: )
(17 mins to read)

P6685 可持久化动态仙人掌的直径问题

题目

给定n, m，求满足$x^m \leq n$的正整数x个数，$n\leq 10^9, m\leq 10^9$

做法

  • m=1, ans = n
  • m>=2时显然答案很小， 所以随便怎么搞就行 ，如果二分的话注意下界从2开始(因为这个t了好几发👀)

P6686 混凝土数学

题目

给定n根木棍的长度$a_i$​，求选择三根构成等腰三角形的方案数(无序对)

做法

显然排序后枚举腰长x然后二分$\lt 2x$的数的个数即可

P6687 论如何玩转 Excel 表格

题目

$2 \times n$的网格，不重复的填入$1 \sim 2n$，现在有一种操作，每次可以选择$2 \times 2$的正方形区域然后旋转$180^\circ$，问从给定网格到目标网格的最少操作次数，或输出无解$n<=10^6$

$$\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \quad$$

$$\begin{bmatrix} 4 & 3 \\ 2 & 1 \end{bmatrix} \quad$$

做法

容易发现对同一个正方形区域操作两次等于不操作，操作一次相当于交换相邻两列，并且两行元素交换。所以不管怎么操作每列的两个元素是固定的，最多上下位置交换一下。考虑当前网格中第i列的两个元素在目标网格中第j列(如果两个元素在不同列，显然无解)，如果j-i为奇数则位置应该颠倒，偶数则位置应该相同。这样扫一遍就可以判定有没有解。可以发现最后就是要让第i列转移到第$p_i$​列，考虑一个排列，每次只能交换相邻两个元素，问使其有序最少需要的操作次数。答案为逆序对个数。设f为一个置换，$f(p) = 1,2,3,…,n$，则答案为$f^{-1}$的逆序对数，树状数组即可

P6688 可重集

题目

给定数组$a_i$​，支持单点修改，并多次询问区间[l1:r1]与区间[l2:r2]是否本质相同。其中本质相同只对这两个区间排序后，对应元素的差值均为整数k。$n<=10^6$

做法

先说一下P3792 由乃与大母神原型和偶像崇拜这题，支持单点修改，并多次询问区间[l:r]在重排后是否是值域连续的。这两道题的特点都是一眼不可做，而解法是数据结构+哈希，所以不能保证一定正确。维护出区间最小值，区间最大值，区间和，区间平方和，然后判断即可从这题的思路容易想到通过维护区间和很容易得到这个差值k，然后再维护平方和？很不幸被出题人卡成了0pts。三次方？没啥用。。考虑设置一个数magic，然后维护$\sum magic^{a_i}$​，然后只要看$\sum_{i=l1}^{r1}magic^{a_i} * magic^k==\sum_{i=l2}^{r2}magic^{a_i}$由于很大要取模，magic和mod随便设就能过。。当然应该能卡上面的方法是把加法利用幂次转成乘法，另一种做法是利用sin。$sin(x+y) = sinxcosy + cosxsiny$$cos(x+y) = cosxcosy − sinxsiny$维护一下$\sum sinx$和$\sum cosx$，同样先利用区间和搞出k，然后用上面的公式判断即可，注意double比较用eps具体怎么维护可以看p6327，区间修改+区间sin和。本题是单点修改+区间sin和由于n是$10^6$级别，而且是单点修+区间查，所以树状数组即可当然以上只是部分可以通过的解法，仅仅是为了拓展一下思路（转成幂次，转成sin）

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#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 = 1e6 + 5;
const ll LINF = 1e18 + 5;
const int magic = 1919810, mod = 1e9 + 7;
inline void mul(int &a, int b) { a = 1ll*a*b%mod; }
inline int Mul(int a, int b) { return 1ll*a*b%mod; }
inline void add(int &a, int b) { a+=b; if(a>=mod) a-=mod; }
inline int Add(int a, int b) { a+=b; if(a>=mod) return a-mod; return a; }
inline void sub(int &a, int b) { a-=b; if(a<0) a+=mod; }
inline int Sub(int a, int b) { a-=b; if(a<0) return a+mod; return a; }
namespace IO
{
  const int MAXSIZE = 1 << 20;
  char buf[MAXSIZE], *p1, *p2;
  inline char gc() { return (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2) ? EOF : *p1++); }
  template <class T> inline void read(T& t)
  {
    t = 0; int f = 1;
    char c = gc();
    while(c>'9'||c<'0') {if(c=='-') f = -f; c = gc();}
    while(c>='0'&&c<='9') t = t*10 + c - 48, c = gc();
    t *= f;
  }
  template <class T> inline void out(T p)
  {
    static int sta[70], tp;
    if(p==0) { putchar('0'); return; }
    if(p<0) { p = -p; putchar('-'); }
    while(p) sta[++tp] = p%10, p/=10;
    while(tp) putchar(sta[tp--]+'0');
  }
}
using namespace IO;
int n, q, a[N], pw[N];
int c[N];
ll sum[N];
void ins(int x, int v)
{
  for(int i=x; i<=n; i+=(i&-i)) add(c[i], v);
}
void del(int x, int v)
{
  for(int i=x; i<=n; i+=(i&-i)) sub(c[i], v);
}
int ask(int x)
{
  int ans = 0;
  for(int i=x; i>0; i-=(i&-i)) add(ans, c[i]);
  return ans;
}
void upd(int x, int v, int op)
{
  for(int i=x; i<=n; i+=(i&-i)) sum[i] += v*op;
}
ll ask2(int x)
{
  ll ans = 0;
  for(int i=x; i>0; i-=(i&-i)) ans += sum[i];
  return ans;
}
ll powmod(ll a, ll b)
{
  ll ans = 1;
  if(b<N) return pw[b];
  while(b)
  {
    if(b&1) ans = ans*a%mod;
    a = a*a%mod;
    b >>= 1;
  }
  return ans;
}
int main()
{
  read(n), read(q);
  pw[0] = 1;
  for(int i=1; i<N; i++) pw[i] = Mul(pw[i-1], magic);
  for(int i=1; i<=n; i++)
  {
    read(a[i]);
    ins(i, pw[a[i]]);
    upd(i, a[i], 1);
  }
  while(q--)
  {
    int op; read(op);
    if(!op)
    {
      int x, y;
      read(x), read(y);
      del(x, pw[a[x]]);
      upd(x, a[x], -1);
      ins(x, pw[a[x]=y]);
      upd(x, a[x], 1);
    }
    else
    {
      int l1, r1, l2, r2;
      read(l1), read(r1), read(l2), read(r2);
      int x = Sub(ask(r1), ask(l1-1)), y = Sub(ask(r2), ask(l2-1));
      ll s1 = ask2(r1) - ask2(l1-1), s2 = ask2(r2) - ask2(l2-1);
      if((s2-s1)%(r1-l1+1)) cout << "NO\n";
      else
      {
        ll k = (s2-s1)/(r1-l1+1);
        if(k<0) k = -k, swap(x, y);
        if(x*powmod(magic, k)%mod==y) cout << "YES\n";
        else cout << "NO\n";
      }
    }
  }
  return 0;
}
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
#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 = 1e6 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 998244353;
const double eps = 1e-6;
namespace IO
{
  const int MAXSIZE = 1 << 20;
  char buf[MAXSIZE], *p1, *p2;
  inline char gc() { return (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2) ? EOF : *p1++); }
  template <class T> inline void read(T& t)
  {
    t = 0; int f = 1;
    char c = gc();
    while(c>'9'||c<'0') {if(c=='-') f = -f; c = gc();}
    while(c>='0'&&c<='9') t = t*10 + c - 48, c = gc();
    t *= f;
  }
  template <class T> inline void out(T p)
  {
    static int sta[70], tp;
    if(p==0) { putchar('0'); return; }
    if(p<0) { p = -p; putchar('-'); }
    while(p) sta[++tp] = p%10, p/=10;
    while(tp) putchar(sta[tp--]+'0');
  }
}
using namespace IO;
int n, q, a[N];
ll sum[N];
double snx[N], csx[N];
inline int sgn(double x) { return (x<-eps ? -1 : x>eps); }
void upd(int x, int v, int op)
{
  double snv = sin(v), csv = cos(v);
  for(int i=x; i<=n; i+=(i&-i))
  {
    sum[i] += v*op;
    snx[i] += snv*op;
    csx[i] += csv*op;
  }
}
ll ask(int x)
{
  ll ans = 0;
  for(int i=x; i>0; i-=(i&-i)) ans += sum[i];
  return ans;
}
pair<double, double> operator - (pair<double, double> a, pair<double, double> b) { return mp(a.fi-b.fi, a.se-b.se); }
pair<double, double> ask2(int x)
{
  double sn = 0.0, cs = 0.0;
  for(int i=x; i>0; i-=(i&-i)) sn += snx[i], cs += csx[i];
  return mp(sn, cs);
}
int main()
{
  read(n); read(q);
  for(int i=1; i<=n; i++)
  {
    read(a[i]);
    upd(i, a[i], 1);
  }
  while(q--)
  {
    int op;
    read(op);
    if(op)
    {
      int l1, r1, l2, r2;
      read(l1); read(r1); read(l2); read(r2);
      ll x = ask(r1) - ask(l1-1);
      ll y = ask(r2) - ask(l2-1);
      if((y-x)%(r1-l1+1)) puts("NO");
      else
      {
        ll k = (y-x)/(r1-l1+1);
        auto p = ask2(r1) - ask2(l1-1);
        auto q = ask2(r2) - ask2(l2-1);
        double snk = sin(k), csk = cos(k);
        if(sgn(q.fi-p.fi*csk-p.se*snk) || sgn(q.se-p.se*csk+p.fi*snk)) puts("NO");
        else puts("YES");
      }
    }
    else
    {
      int x, y;
      read(x); read(y);
      upd(x, a[x], -1);
      upd(x, a[x]=y, 1);
    }
  }
  return 0;
}