7.30集训

Posted on Edited on In

#上午

第一题

巧克力

这题某谷数据水，\(int\)就过了，因为以前做过，所以这次理所当然的切了

切了之后我还仔细查看是否需要LL，检查无误后，没开LL

但是教练的数据强，卡我50分，上次因为LL卡我100分

出题人学长Youngsc的题是真的强.....

这题贪心做，把权值从小到大排序，排完之后干就完了

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
#include <bits/stdc++.h>
// #define debug
#define int long long
#define LL long long
using namespace std;

LL in() {
   LL x = 0, f = 1; char ch;
   while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
   for(x = ch^48;isdigit(ch = getchar()); x = (x<<1)+(x<<3) + (ch^48));
   return x * f;
}

const int N = 1e5+10;

int n, m, res;
int sum1 = 1, sum2 = 1;

struct node{int val, tag;}a[N];

inline int cmp (node x, node y) {return x.val > y.val;}

signed main () {
   n = in(), m = in();
   for (int i = 1; i <= n-1; ++ i) a[i].val = in(), a[i].tag = 1;
   for (int i = n; i <= n+m-2; ++ i) a[i].val = in(), a[i].tag = 2;
   sort (a+1, a+n+m-1, cmp);
#ifdef debug
for (int i = 1; i <= n+m-2; ++ i)
   cout << "val-->" << a[i].val << "tag-->" << a[i].tag << '\n';
#endif
   for (int i = 1; i <= n+m-2; ++ i) {
      if (a[i].tag == 1) res += a[i].val*sum2, ++ sum1;
      else res += a[i].val*sum1, ++ sum2;
   }
   cout << res;
   return 0;
}

第二题

Sample input 
5 6
7 2 3 1 1
5 0 6 0 0
8 6 6 5 3
4 3 7 8 2
4 0 0 6 9
Sample output 
20

样例解释: 分别以\((2,1)\)为左上角\((5,2)\)为右下角和以\((1,3)\)为左上角以\((4,5)\)为右下角的两个矩阵。

数据范围:

对于\(20%\)的数据\(n \leq 5\)

对于\(50%\)的数据\(n \leq 50\)

另有\(5%\)的数据满足所有电脑的便利值均为\(1\)

另另有\(25%\)的数据满足所有的电脑便利值相同

对于\(100%\)的数据满足\(n \leq 300\)，\(p \leq 50\)，\(0 \leq a[i][j] \leq 65536\)

特别鸣谢lpj大佬，在我写完代码之后依旧迷迷糊糊的时候，帮我理清了思路

首先对于这个题，观察数据范围发现\(n\leq300,p\leq50,0\leq a[i][j]\leq65536\)

我们可以考虑一个\(n^4\)的dp暴力，直接搞

但是这样是过不了全部数据的

\(n \leq 300\)我们考虑如何来优化一维

我们考虑用\(l\)和\(r\)这两维来搞那个矩形长度，对于每一行，我们把那一行看成一个元素，对那一行求一个前缀和

这样再从纵列枚举一个\(t\)这样就转化成了三维

我们来考虑主函数中的三个函数
function 
shuruyijichushihua()
jiejuewenti()
shuchudaan()

其中第一个与第三个函数很简单

我们来看jiejuewenti的函数
function 
dodododo()
fanzhuan()
dododo()

先说明一下fanzhuan()，对于矩形一上一下的情况，我们必须将矩阵翻转过来，再干一遍

翻转可以有两种写法：

way1:
Code 
a[i][j] ^= a[j][i] ^= a[i][j] ^= a[j][i];

way2:

Code 
int x = a[i][j], y = a[j][i];
x ^= y;
y ^= x;
x ^= y;
a[i][j] = x;
a[j][i] = y;

表达意思是一样的

来看dodododo的函数

首先我们需要对每一行都搞一个前缀和，

1
2
3
4
5
for (int i = 1; i <= n; ++ i) {
   for (int j = 1; j <= n; ++ j) {
      sum[i][j] = a[i][j], sum[i][j] += sum[i][j-1];
   }
}

考虑用\(l, r\)来枚举当前这个矩形的长，枚举一个\(i\)来搞矩形的宽

这样我们就很好的可以枚举到每一个矩形的面积

对于当前枚举到的矩形的面积（\(zonghe += sum[i][r] - sum[i][l-1]\)）

我们再来考虑搞一个记忆化的数组\(t\)，我们给p以内的数字都打上标记-1，

设k为当前总和模p之后的数字，考虑\(t[k]\)是否为-1

如果发现为-1，那就是以前没有出现过，我们更新标记\(t[k] = i\),表示上一次出现模p得到k的情况是i

如果发现\(t[k]\)不为-1，那么会有两种情况，

第一种：模p为0，是p的倍数

第二种：以前出现过模p得到k的情况

所以我们对于上面两种情况都可以更新答案

那么如何更新答案？

我们定义两个数组\(f,g\)其中\(f[i]\)表示紧贴着\(i\)这条直线的左边的最大矩形

\(g[i]\)表示\(i\)这条直线的右边的最大矩形（不一定紧贴）

\(f[r]\)是紧贴着\(r\)这条线的左边的矩形的最大面积，\((r-l+1)*(i-t[k])\)不就是当前枚举到的最大面积吗？

更新就完事了

\(g[l]\)是\(l\)这条线右边的矩形的最大面积，和f数组一样，\((r-l+1)*(i-t[k])\)更新就完事了（注意当前还是紧贴着的，而我们\(g[i]\)的定义是贴不贴着i这条线都可以，所以我们的g数组一定还会更新）

当我们所有矩形都查找完毕之后，考虑再次更新\(g\)数组，至于为什么更新上文提到了已经

务必要倒序枚举，因为你如果顺序枚举的话，当前的答案可能会受到之后的答案的影响，所以当前答案就不是最优的

对于整体的真正答案，\(res = max(res, f[i]+g[i+1])\)，为什么要\(i+1\)？

再次考虑\(g\)数组定义：表示\(i\)这条直线的右边的最大矩形（不一定紧贴）

不一定紧贴，万一紧贴了呢？两条边有重叠不就不满足题意了吗？所以要用\(g[i+1]\)。

PS:

对于为什么在“第二种：以前出现过模p得到k的情况”的时候也要更新答案？“

我们重新考虑题意：一块矩形的和是p的倍数，也就是模p为零

可以用式子表示为：

\(s_{当前} - s_{上一次} \equiv 0 (mod p)\)

进一步转化为：

\(s_{当前} \equiv s_{上一次} (mod p)\)

所以可理解为，只要上一次和这一次在模p意义的数字一样，就可以更新答案了，因为他们相减之后一定是p的倍数，可手跑几组例子

至此，关于“第二种：以前出现过模p得到k的情况”的时候也要更新答案？”这句话，也就不难理解了

给出\(youngsc\)的代码：

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
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
# define R register
# define LL long long

using namespace std;

int n,p,a[310][310],f[310],g[310],ans,t[60],x[310][310];

template <typename T> inline void in(R T& a){
   R char c=getchar(); R T x=0,f=1;
   while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
   while (isdigit(c)) x=(x<<1)+(x<<3)+c-'0',c=getchar();
   a=x*f;
}

template <typename T> inline void maxx(R T&a,R T b){a<b? a=b:0;}

inline void solve(){
   for (R int i=1; i<=n; ++i) f[i]=g[i]=0;
   for (R int i=1; i<=n; ++i)
      for (R int j=1; j<=n; ++j)
         a[i][j]=x[i][j],a[i][j]+=a[i][j-1];
   for (R int l=1; l<=n; ++l) {
      for (R int r=l; r<=n; ++r) {
         R int sum=0;
	 for (R int i=1; i<p; ++i) t[i]=-1;
	 for (R int i=1; i<=n; ++i) {
	    sum += a[i][r]-a[i][l-1];
	    sum %= p;
	    if (t[sum]!=-1) maxx(f[r],(r-l+1)*(i-t[sum])),maxx(g[l],(r-l+1)*(i-t[sum]));
	    else t[sum] = i;
	 }
      }
   }
   for (R int i=n-1; i; --i) maxx(g[i],g[i+1]);
   for (R int i=1; i<n; ++i) maxx(ans,f[i]+g[i+1]);
}

int main(){
   in(n),in(p);
   for (R int i=1; i<=n; ++i)
      for (R int j=1; j<=n; ++j)
         in(x[i][j]);
   solve();
   for (R int i=1; i<=n; ++i)
      for (R int j=i+1; j<=n; ++j) 
	 x[i][j] ^= x[j][i] ^= x[i][j] ^= x[j][i];
   solve();
   printf("%d",ans);
   return 0;
}

\(7.31update\)

自己写了一遍，给出自己的代码

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
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

const int N = 321;

int n, p, res;
int f[N], g[N], t[N];
int a[N][N], sum[N][N];

inline void shuruyijichushihua(){
   cin >> n >> p;
   for (int i = 1; i <= n; ++ i) {
      for (int j = 1; j <= n; ++ j) {
         cin >> a[i][j];
      }
   }
}

inline void dododo() {
   for (int i = 1; i <= n; ++ i) f[i] = g[i] = 0;
   for (int i = 1; i <= n; ++ i) {
      for (int j = 1; j <= n; ++ j) {
          sum[i][j] = a[i][j], sum[i][j] += sum[i][j-1];
      }
   }
   for (int l = 1; l <= n; ++ l) {
      for (int r = l; r <= n; ++ r) {
         int zonghe = 0;
         for (int i = 1; i < p; ++ i) t[i] = -1;
         for (int i = 1; i <= n; ++ i) {
            zonghe += sum[i][r] - sum[i][l-1];
	    zonghe %= p;
            if (t[zonghe] != -1) {
	       f[r] = max(f[r], (r-l+1)*(i-t[zonghe]));
	       g[l] = max(g[l], (r-l+1)*(i-t[zonghe]));
            } else t[zonghe] = i;
         }
      }
   }
   for (int i = n-1; i; -- i) g[i] = max(g[i], g[i+1]);
   for (int i = 1; i != n-1; ++ i) res = max(res, f[i]+g[i+1]);
}

inline void fanzhuan() {
   for (int i = 1; i <= n; ++ i) {
      for (int j = i+1; j <= n; ++ j) {
	 // a[i][j] ^= a[j][i] ^= a[i][j] ^= a[j][i];
         int x = a[i][j], y = a[j][i];
         x ^= y;
	 y ^= x;
	 x ^= y;
	 a[i][j] = x;
	 a[j][i] = y;
      } 
   }
}

inline void jiejuewenti() {
   dododo();
   fanzhuan();
   dododo();
}

inline void shuchudaan(){cout << res;}

inline int thestars() {
// freopen ("matrix.in", "r", stdin);
// freopen ("matrix.out", "w", stdout);
   shuruyijichushihua();
   jiejuewenti();
   shuchudaan();
   fclose (stdin), fclose (stdout);
   return 0;
}

int youngore = thestars();

signed main() {;}

\(8.3update\)

给出\(youngsc\)的题解：

20pts:暴力枚举矩阵

50pts:可以采用正解中的部分做法优化暴力枚举的做法

Special 5pts:这部分其实就相当于数学题了，与形状无关，只需考虑是不是存在最大的矩阵使得面积是p的倍数就可以了

Special 25pts:同上

100 pts:

首先我们考虑一个弱化版的问题，如果我们只需要选择一块区域使得电脑台数最多该怎么办？

首先我们对矩阵中的每一行都做一个前缀和，那么对于任意单独一行的任意一个区间都可以在的时间内求出区间内的数字之和。

那么我们就可以先 \(a_i\) 枚举所求矩阵的左右边界，当左右边界确定后，我们可以在每一行的前缀和的辅助下快速求出每一行在这个边界限制下的区间和，即将其变成一个数字，便可以将矩阵压缩为一个纵向的一维数组

紧接着我们需要做的就是找到一个在这个一维数组中找到一个尽可能大的区间使得区间和是𝑝的倍数。我们依然考虑前缀和，定义𝑓𝑖表示数组中前𝑖项和对𝑝取模之后的值，由此我们可知，如果存在𝑥和𝑦使得𝑓𝑥=𝑓𝑦且𝑥<𝑦，则由前缀和定义以及取模性质可知\(\begin{aligned}\sum_{x+1} ^ y a_i\% p = 0\end{aligned}\)，即该区间和为𝑝的倍数。那么我们可以想到对于每一个固定的𝑦，我们只需要找到最小的𝑥使得𝑥<𝑦且𝑓𝑥=𝑓𝑦，那么这个区间就是以𝑦为右边界且区间和为𝑝的倍数的最大区间。而这个过程我没只需要从前往后扫一遍，维护一下对于𝑝取模后的每一个值在𝑓𝑖中出现的最早位置，同时查找一下与当前𝑓𝑖相等的最早出现的位置，二者做差即可，这个过程是𝑂(𝑛)的，这样我们便可以\(𝑂(𝑛^3)\)地求出面积最大的满足和是𝑝地倍数地矩阵。

当我们需要找到两个互不重叠的矩阵时该怎么办呢？首先我们可以想到，这两个矩阵地位置关系一定是上下或者左右，即必然存在一条竖直或者水平的分界线将这两个矩阵分隔开。对于左右地情况，我们维护两个数组𝑓和𝑔，𝑓𝑖表示以𝒊为右边界的符合条件的最大矩阵，𝑔𝑖表示以𝒊或者大于𝒊为左边界的符合条件的最大矩阵，注意二者定义有所不同。𝑓𝑖的求法很简单，只需要在上述预处理的过程中维护就行了，𝑔𝑖也和𝑓𝑖求法一样，只需要对这个数组再维护一下最大后缀和就可以了。有了这两个数组，我们只要枚举𝑖求出𝑓𝑖+𝑔𝑖的最大值就可以了，这个值时左右布局时候的答案，上下布局的话，我们将整个矩阵关于主对角线对称一下，然后从头开始重新进行一边这样的操作，最后两种情况取最大值。

End.

第三题

Sample input 
6 12
0 1 1 1 1 0
2 4 0
1 3 0
1 6 3
4 5 2
3 4 6
2 5 4
4 3 9
3 1 3
2 5 5
6 1 9
1 2 7
2 1 8
Sample input 
3 0
0 8
6 3
2 12
-1 -1
9 9

给出\(Youngsc\)的代码： 

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
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
# define R register
# define LL long long
# define inf 200000000
# define N 50010

using namespace std;

int n,m,x,y,z,e,h[N],t[N],f[N],ans[N][2],dis[N];

struct zx{int v,w,pre;} ed[N*7];
struct yy{
   int x,w;
   bool operator < (const yy y) const {return w>y.w;}
};
bool vis[N];
//priority_queue <yy> q;
queue <int> q;
template <typename T> inline void in(R T& a){
   R char c=getchar(); R T x=0,f=1;
   while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
   while (isdigit(c)) x=(x<<1)+(x<<3)+c-'0',c=getchar();
   a=x*f;
}

template <typename T> inline void maxx(R T&a,R T b){a<b? a=b:0;}
template <typename T> inline void minn(R T&a,R T b){a>b? a=b:0;}

inline void add(R int x,R int y,R int z){
   ed[++e] = (zx){y,z,h[x]};
   h[x] = e;
}

inline void dij(R int a,R int b,R int c){
   for (R int i=1; i<=n; ++i) if (t[i]==a&&f[i]==b) dis[i]=0,q.push(i); else dis[i]=inf;
   while (!q.empty()){
      R int x=q.front();
      q.pop();
      for (R int i=h[x]; i; i=ed[i].pre) {
         R int v=ed[i].v;
         if (dis[v] > dis[x]+ed[i].w) {
            dis[v]=dis[x]+ed[i].w;
            if (!vis[v]) vis[v]=1,q.push(v);
         }
      }
      vis[x]=0;
   }
   for (R int i=1; i<=n; ++i) if (t[i]==c&&f[i]!=b) minn(ans[i][a^c],dis[i]);
}

int main(){
   in(n),in(m);
   for (R int i=1; i<=n; ++i) in(t[i]),ans[i][0]=ans[i][1]=inf;
   for (R int i=1; i<=m; ++i) in(x),in(y),in(z),add(y,x,z);
   for (R int p=0; p<=15; ++p) {
      for (R int i=1; i<=n; ++i) if ((i>>p)&1) f[i]=1; else f[i]=0;
	 dij(0,0,0); dij(0,0,1);
	 dij(0,1,0); dij(0,1,1);
	 dij(1,0,0); dij(1,0,1);
	 dij(1,1,0); dij(1,1,1);
   }
   for (R int i=1; i<=n; ++i,printf("\n")) {
      if (ans[i][0] == inf) printf("-1 "); else printf("%d ",ans[i][0]);
      if (ans[i][1] == inf) printf("-1"); else printf("%d",ans[i][1]);
   }
   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
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

const int N = 1e5+66, INF = 214748364;

int n, m, a[N];
int vis[N], dis[N], tot[N];
int ans[N][6];

queue<int>q;

struct node {int to, val, nxt;}e[N]; int cnt, head[N];

inline void jiabian(int u, int v, int c) {
   ++ cnt;
   e[cnt].to = v, e[cnt].val = c;
   e[cnt].nxt = head[u], head[u] = cnt;
}

inline void shuruyijichushihua() {
   cin >> n >> m;
   for (int i = 1; i <= n; ++ i) {
      scanf ("%d", &a[i]);
      ans[i][0] = ans[i][1] = INF;
   }
   for (int i = 1; i <= m; ++ i) {
      int x, y, z;
      cin >> x >> y >> z;
      jiabian (x, y, z);
   }
}

inline void zuiduanlusuanfa(int t, int b, int s) {
   for (int i = 1; i <= n; ++ i) {
      dis[i] = INF;
      if (a[i] == t && tot[i] == b)  {
      	 q.push(i);
	 vis[i] = true;
	 dis[i] = 0;
      }
   }
   while(q.size()) {
      int x = q.front(); q.pop();
      vis[x] = false;
      for (int i = head[x]; i; i = e[i].nxt) {
         int y = e[i].to;
	 if (dis[x]+e[i].val<dis[y]) {
	    dis[y] = dis[x]+e[i].val;
	    if (!vis[y]) {
	   	vis[y] = 1;
	   	q.push(y);
	    }
         }
      }
   }
   for (int i = 1; i <= n; ++ i) {
      if (a[i] == s && tot[i] != b) {
	 if (ans[i][t^s] > dis[i])
	    ans[i][t^s] = dis[i];
      }
   }
}

inline void dodododo() {
   zuiduanlusuanfa(0, 0, 0); zuiduanlusuanfa(0, 0, 1);
   zuiduanlusuanfa(0, 1, 0); zuiduanlusuanfa(0, 1, 1);
   zuiduanlusuanfa(1, 0, 0); zuiduanlusuanfa(1, 0, 1);
   zuiduanlusuanfa(1, 1, 0); zuiduanlusuanfa(1, 1, 1);
}

inline void jiejuewenti() {
   for (int i = 0; i < 15; ++ i) {
      for (int j = 1; j <= n; ++ j) {
	 tot[j] = (j>>i)&1;
      }
      dodododo();
   }
}

inline void shuchudaan() {
   for (int i = 1; i <= n; ++ i) {
      if (ans[i][0] == INF) cout << "-1 ";
      else cout << ans[i][0] << ' ';
      if (ans[i][1] == INF) puts("-1");
      else cout << ans[i][1] << '\n';
   }
   return;
}

inline int thestars() {
   shuruyijichushihua();
   jiejuewenti();
   shuchudaan();
   fclose (stdin), fclose (stdout);
   return 0;
}

int youngore = thestars();

signed main() {;}

给出\(youngsc\)的题解：

可以创建一个虚点A，A指向所有A党城市，边权为0，其它正常边反着连，从这个虚点A跑一个最短路dij，到其它B党城市的距离，就是B党城市到最近A党城市的距离。

求B党城市到A党同理。

但是你发现他还要求你求出友好城市的距离，由于不能把自己算进去，所以这个不能直接搞出来。注意到n只开到五万而时限有2秒，所以两个log没问题。注意到每个点都有个编号，我们考虑按位选点进行多源最短路。还是反着建边，因为正着建边的最短路是一到多，而反着建边的最短路就是多到一的最短了，符合题目要求。

例如，将第?位为0的所有A阵营的点作为源扔进去跑最短路（可以理解为从一个超级源向这些点连了长度为0的边）然后用它更新所有第?位为1的点。这样能保证不会用自己求自己。

复杂度为\(O(nlog^2n)\)，其中\(nlogn\)是\(dij\)，另外\(logn\)是按位给点分拨

End.

下午

讲了分块莫队

分块大致思想：说白了就是一种暴力，一种温文尔雅的暴力

我们正常对序列进行某种操作，假如你不会什么线段树猫树树状数组，反正一堆树与数

我们貌似就只能\(O(n^2)\)了，给你个\(1e5\)的数据不\(T\)飞才怪

我们考虑如何来优化，首先对一个整体区间进行分块，块长\(len\) = \(\sqrt{n}\)，所以块的数量为\(\sqrt{n}\)

对于一个极大的区间，我们将他们分块对待，对左半部分的残缺，我们暴力修改

对于右半部分的残缺，我们暴力修改，而对于中间部分的整块，我们特殊对待，打上\(tag\)

本质上是基于暴力的，所以很好理解

给出大致代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void xiugai(int L, int R, int val) {
   if (pos[L] == pos[R]) {
      //do do do..
      return;
   }
   for (int i = L; i <= pos[L]*len; ++ i) //do do do...
   for (int i = pos[L]+1; i <= pos[R]-1; ++ i)//do do do...
   for (int i = (pos[R]-1)*len+1; i <= R; ++ i)//do do do...
}
inline void chaxun(int now) {cout << a[now]+tag[pos[now]];}
inline int thestars() {
   cin >> n;
   len = sqrt(n);
   for (int i = 1; i <= n; ++ i) {
      cin >> a[i];
      pos[i] = (i-1)/len+1;
   }
   xiugai(l, r, c);
   chaxun(x);
   return 0;
}

分析代码：

修改的时候首先对于两个端点，如果发现首尾在一个块内，暴力干就完了

如果不在一个块内，左-中-右，开始干，期间维护标记啥的

查询的时候输出要查询的键值，然后加上标记之类的

分块例题：数列分块入门\(1\)~\(9\)

下面来例个分析：

第一个

click

区间加，单点查，秒切

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
#include <bits/stdc++.h>
#define N 600000
using namespace std;
signed n, len;
int pos[N], tag[N], a[N];

inline void add (int L, int R, int val) {
   if (pos[L] == pos[R]) {
      for ( int i = L;i<=R;++i) a[i] += val;
      return;
   }
   for ( int i = L;i<=pos[L]*len;++i) a[i] += val;
   for ( int i = pos[L]+1;i<=pos[R]-1;++i) tag[i] += val;
   for ( int i = (pos[R]-1)*len+1;i<=R;++i) a[i] += val;
}

signed main () {
   n = Read (), len = sqrt(n);
   for ( int i = 1;i<=n;++i) a[i] = Read (), pos[i] = (i - 1)/len + 1;
   for ( int i = 1;i<=n;++i) {
      int opt, l, r, c;
      opt = Read (), l = Read (), r = Read (), c = Read ();
      if (!opt) add (l, r, c);
      else Put (a[r] + tag[pos[r]]);
   }
   return 0;
}

第二个

click

我们考虑对原数组再开一个新数组来维护，

查询的时候

对于整块，我们给他排序，然后在排完序的序列里面二分查找小于val的数的个数

对于散块，暴力找

修改的时候

对于整块，我们给原数组和排完序之后的数组都要加上tag标记

对于散块，暴力加，加完之后，再排完序赋给排序数组

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
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

const int N = 1e5 + 66;

int n, m, len, a[N];
int pos[N], paixu[N];
int tag[N];

inline void shuruyijichushihua() {
    cin >> n;
    len = sqrt(n);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        paixu[i] = a[i];
        pos[i] = (i - 1) / len + 1;
    }
    for (int i = 1; i <= pos[n]; ++i) {
        int s = (i - 1) * len + 1, t = i * len;
        sort(paixu + s, paixu + t + 1);
    }
    int now = (pos[n] - 1) * len + 1;
    sort(paixu + now, paixu + n + 1);
}

inline void zaimougequjianjiashangyigeshu(int L, int R, int val) {
    int s = 0, t = 0;
    if (pos[L] == pos[R]) {
        for (int i = L; i <= R; ++i) a[i] += val;
        s = (pos[L] - 1) * len + 1, t = pos[L] * len;
        for (int i = s; i <= t; ++i) paixu[i] = a[i];
        sort(paixu + s, paixu + t + 1);
        return;
    }
    for (int i = L; i <= pos[L] * len; ++i) a[i] += val;
    s = (pos[L] - 1) * len + 1, t = (pos[L] * len);
    for (int i = s; i <= t; ++i) paixu[i] = a[i];
    sort(paixu + s, paixu + t + 1);
    for (int i = pos[L] + 1; i <= pos[R] - 1; ++i) tag[i] += val;
    for (int i = (pos[R] - 1) * len + 1; i <= R; ++i) a[i] += val;
    s = (pos[R] - 1) * len + 1, t = pos[R] * len;
    for (int i = s; i <= t; ++i) paixu[i] = a[i];
    sort(paixu + s, paixu + t + 1);
}

inline int xiaoyumougeshudegeshu(int L, int R, int who) {
    int res(0);
    if (pos[L] == pos[R]) {
        for (int i = L; i <= R; ++i)
            if (a[i] + tag[pos[R]] < who)
                ++res;
        return res;
    }
    for (int i = L; i <= pos[L] * len; ++i)
        if (a[i] + tag[pos[L]] < who)
            ++res;
    for (int i = pos[L] + 1; i <= pos[R] - 1; ++i) {
        int now = (i - 1) * len + 1, to = i * len;
        int chazhao = lower_bound(paixu + now, paixu + to + 1, (who - tag[i])) - paixu;
        res += chazhao - now;
    }
    for (int i = (pos[R] - 1) * len + 1; i <= R; ++i)
        if (a[i] + tag[pos[R]] < who)
            ++res;
    return res;
}

inline void jiejuewentiyijishuchu() {
    for (int i = 1; i <= n; ++i) {
        int opt, l, r, c;
        cin >> opt >> l >> r >> c;
        if (opt == 0)
            zaimougequjianjiashangyigeshu(l, r, c);
        else
            cout << xiaoyumougeshudegeshu(l, r, c * c) << '\n';
    }
}

inline int thestars() {
    shuruyijichushihua();
    jiejuewentiyijishuchu();
    return 0;
}

int youngore = thestars();

signed main() { ; }

自己写了一遍，坑很多，比如，我们排序的时候的数组，还有我们必须给原数组修改，然后赋值给那一段区间，再排序 建议以后把每个块的左右端点都开个数组就好了

第三个

click

前驱：比ta小的最大的元素

感觉和第二个一样，维护两个数组就好

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
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

const int N = 1e5 + 66;

int n, m, len, a[N];
int pos[N], paixu[N];
int tag[N];

inline void shuruyijichushihua() {
   cin >> n;
   len = sqrt(n);
   for (int i = 1; i <= n; ++i) {
      cin >> a[i];
      paixu[i] = a[i];
      pos[i] = (i - 1) / len + 1;
   }
   for (int i = 1; i < pos[n]; ++i) {
      int s = (i - 1) * len + 1, t = i * len;
      sort(paixu + s, paixu + t + 1);
   }
   int now = (pos[n] - 1) * len + 1;
   sort(paixu + now, paixu + n + 1);
}

inline void zaimougequjianjiashangyigeshu(int L, int R, int val) {
   int s = 0, t = 0;
   if (pos[L] == pos[R]) {
      for (int i = L; i <= R; ++i) a[i] += val;
      s = (pos[L] - 1) * len + 1, t = pos[L] * len;
      for (int i = s; i <= t; ++i) paixu[i] = a[i];
      sort(paixu + s, paixu + t + 1);
      return;
   }
   for (int i = L; i <= pos[L] * len; ++i) a[i] += val;
   s = (pos[L] - 1) * len + 1, t = (pos[L] * len);
   for (int i = s; i <= t; ++i) paixu[i] = a[i];
   sort(paixu + s, paixu + t + 1);
   for (int i = pos[L] + 1; i <= pos[R] - 1; ++i) tag[i] += val;
   for (int i = (pos[R] - 1) * len + 1; i <= R; ++i) a[i] += val;
   s = (pos[R] - 1) * len + 1, t = pos[R] * len;
   for (int i = s; i <= t; ++i) paixu[i] = a[i];
   sort(paixu + s, paixu + t + 1);
}
inline int xiaoyumougeshudegeshu(int L, int R, int who) {
   int res(-1), s(0), t(0);
   if (pos[L] == pos[R]) {
      for (int i = L; i <= R; ++i)
         if (a[i]+tag[pos[L]] < who) res = max(res, a[i]+tag[pos[L]]);
      return res;
   }
   s = L, t = pos[L]*len;
   for (int i = s; i <= t; ++i)
      if (a[i]+tag[pos[L]] < who) res = max(res, a[i]+tag[pos[L]]);
   for (int i = pos[L] + 1; i <= pos[R] - 1; ++i) {
      s = (i - 1) * len + 1, t = i * len;
      int now = lower_bound(paixu+s, paixu+t+1, (who-tag[i])) - paixu;
      -- now;
      res = (now==s-1)?res:(res>paixu[now]+tag[i])?res:paixu[now]+tag[i];
   }
   s = (pos[R]-1)*len+1, t = R;
   for (int i = s; i <= t; ++i)
      if (a[i]+tag[pos[R]] < who) res = max(res, a[i]+tag[pos[R]]);
   return res;
}

inline void jiejuewentiyijishuchu() {
   for (int i = 1; i <= n; ++i) {
      int opt, l, r, c;
      cin >> opt >> l >> r >> c;
      if (opt == 0) zaimougequjianjiashangyigeshu(l, r, c);
      else cout << xiaoyumougeshudegeshu(l, r, c) << '\n';
    }
}

inline int thestars() {
   shuruyijichushihua();
   jiejuewentiyijishuchu();
   return 0;
}

int youngore = thestars();

signed main() { ; }

\(8.2update\):

自己打了一遍，靠，真的细节真多：

1.在块里面更新答案的时候，必须加上tag标记

2.\(sort\)，\(lower\)_\(bound\)都是左闭右开的

第四个

click

一眼板子，模的时候最后进行

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
#include <bits/stdc++.h>
#define int long long
// #define debug
using namespace std;

const int N = 1e5+66;

int n, m, len, a[N];
int pos[N], sum[N], tag[N];

inline void add(int L, int R, int val) {
   int x = pos[L], y = pos[R];
   if (x == y) {
      for (int i = L; i <= R; ++ i) a[i] += val;
      sum[x] += val*(R-L+1);
      return;
   }
   for (int i = L; i <= x*len; ++ i) a[i] += val;
   sum[x] += val*(x*len-L+1);
   for (int i = x+1; i <= y-1; ++ i) tag[i] += val;
   for (int i = (y-1)*len+1; i <= R; ++ i) a[i] += val;
   sum[y] += val*(R-((y-1)*len+1)+1);
   return;
}

inline int get_sum(int L, int R, int mod) {
   int x = pos[L], y = pos[R], res(0);
   if (x == y) {
      int res(0);
      for (int i = L; i <= R; ++ i) res += (tag[pos[i]]+a[i]);
      return res%mod;
   }
   for (int i = L; i <= x*len; ++ i) res += (tag[pos[i]]+a[i]);
   for (int i = x+1; i <= y-1; ++ i) res += sum[i] + tag[i]*len;
   for (int i = (y-1)*len+1; i <= R; ++ i) res += (tag[pos[i]]+a[i]);
   return res%mod;
}

inline void shuru() {
   cin >> n;
   len = sqrt(n);
   for (int i = 1; i <= n; ++ i) {
      scanf ("%lld", &a[i]);
      pos[i] = (i-1)/len+1;
      sum[pos[i]] += a[i];
   }
}

inline void jiejue() {
    for (int i = 1; i <= n; ++ i) {
      int opt, l, r, c;
      scanf ("%lld%lld%lld%lld", &opt, &l, &r, &c);
      if (!opt) add(l, r, c);
      else cout << get_sum(l, r, c+1) << '\n';
   }
}

inline int thestars() {
   shuru();
   jiejue();
   return 0;
}

int youngore = thestars();

signed main() {;}

\(8.2update\):

时隔半年，重新手写了一遍，发现几个问题：

1.在区间修改的时候，\(tag\)数组进行维护，但是不用动\(sum\)数组（维护整块的时候）

2.查询整块的时候，输出\(sum+tag*len\)

第五个

click

显然，一个数开方不会超过六次就会变成1

如果每次区间开方的数不涉及完整块，意味着不超过\(2\sqrt{n}\)个元素，直接暴力

如果涉及了完整的块，这些块经过几次操作之后，都会变成1，所以我们需要记录这些块经过每次操作之后，区间里面是不是都变成了1，如果是的话，那么我们以后需要查询这些块，只需要加上\(1*len\)就可以了

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
// by hzw
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 998244353
#define pi acos(-1)
#define inf 0x7fffffff
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,blo;
int bl[50005];
int v[50005],sum[50005],flag[50005];
void solve_sqrt(int x)
{
    if(flag[x])return;
    flag[x]=1;
    sum[x]=0;
    for(int i=(x-1)*blo+1;i<=x*blo;i++)
    {
        v[i]=sqrt(v[i]),sum[x]+=v[i];
        if(v[i]>1)flag[x]=0;
    }
}
void add(int a,int b,int c)
{
    for(int i=a;i<=min(bl[a]*blo,b);i++)
    {
        sum[bl[a]]-=v[i];
        v[i]=sqrt(v[i]);
        sum[bl[a]]+=v[i];
    }
    if(bl[a]!=bl[b])
        for(int i=(bl[b]-1)*blo+1;i<=b;i++)
        {
            sum[bl[b]]-=v[i];
            v[i]=sqrt(v[i]);
            sum[bl[b]]+=v[i];
        }
    for(int i=bl[a]+1;i<=bl[b]-1;i++)
        solve_sqrt(i);
}
int query(int a,int b)
{
    int ans=0;
    for(int i=a;i<=min(bl[a]*blo,b);i++)
        ans+=v[i];
    if(bl[a]!=bl[b])
        for(int i=(bl[b]-1)*blo+1;i<=b;i++)
            ans+=v[i];
    for(int i=bl[a]+1;i<=bl[b]-1;i++)
        ans+=sum[i];
    return ans;
}
int main()
{
    n=read();blo=sqrt(n);
    for(int i=1;i<=n;i++)v[i]=read();
    for(int i=1;i<=n;i++)
    {
        bl[i]=(i-1)/blo+1;
        sum[bl[i]]+=v[i];
    }
    for(int i=1;i<=n;i++)
    {
        int f=read(),a=read(),b=read(),c=read();
        if(f==0)add(a,b,c);
        if(f==1)
            printf("%d\n",query(a,b));
    }
    return 0;
}

第六个

click

考虑，插入一个数的话，分块需要\(O(n)\)，而对于链表来说的话，只需要\(O(1)\)

考虑，查询一个数的话，分块只需要\(O(1)\)，而对于链表来说的话，需要\(O(n)\)

考虑，将分块与链表结合起来，---->块状链表

块状链表应该至少支持：分裂、插入、查找。 什么是分裂？分裂就是分裂一个\(node\) ，变成两个小的 \(node\) ，以保证每个 \(node\) 的大小都接近 \(O(\sqrt{n})\)（否则可能退化成普通数组）。当一个 \(node\)的大小超过\(2*\sqrt{n}\) 时执行分裂操作。

块状链表即插入\(O(\sqrt{n})\)，查询\(O(\sqrt{n})\)，将链表与分块的优缺点融合了一下

1
2
3
4
5
6
7
struct node {
  node* nxt;
  int size;
  char d[(sqn << 1) + 5];
  node() { size = 0, nxt = NULL, memset(d, 0, sizeof(d)); }
  void pb(char c) { d[size++] = c; }
};

查询的时候，挨个块的找，最多\(O(\sqrt{n})\)，插入的时候\(O(\sqrt{n})\)

分裂操作怎么做呢？先新建一个节点，再把被分裂的节点的后\(O(\sqrt{n})\)个值复制到新节点，然后把被分裂的节点的后\(O(\sqrt{n})\)个值删掉（ \(-- size\)），最后把新节点插入到被分裂节点的后面即可

块状链表的所有操作的复杂度都是\(O(\sqrt{n})\)的。

第七个

click

一眼线段树，维护一个乘法标记和一个加法标记，下放标记的时候先下放乘法再下放加法

线段树会写，分块不会写

若当前的一个块乘以\(m_1\)后加上\(a_1\)，这时进行一个乘\(m_2\)的操作，则原来的标记变成\(m_1*m_2\)，\(a_1*m_2\)

若当前的一个块乘以\(m_1\)后加上\(a_1\)，这时进行一个加\(a_2\)的操作，则原来的标记变成\(m_1\)，\(a_1+a_1\)

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
//by hzw
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 10007
#define pi acos(-1)
#define inf 0x7fffffff
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,blo;
int v[100005],bl[100005],atag[1005],mtag[1005];
void reset(int x)
{
    for(int i=(x-1)*blo+1;i<=min(n,x*blo);i++)
        v[i]=(v[i]*mtag[x]+atag[x])%mod;
    atag[x]=0;mtag[x]=1;
}
void solve(int f,int a,int b,int c)
{
    reset(bl[a]);
    for(int i=a;i<=min(bl[a]*blo,b);i++)
    {
        if(f==0)v[i]+=c;
        else v[i]*=c;
        v[i]%=mod;
    }
    if(bl[a]!=bl[b])
    {
        reset(bl[b]);
        for(int i=(bl[b]-1)*blo+1;i<=b;i++)
        {
            if(f==0)v[i]+=c;
            else v[i]*=c;
            v[i]%=mod;
        }
    }
    for(int i=bl[a]+1;i<=bl[b]-1;i++)
    {
        if(f==0)atag[i]=(atag[i]+c)%mod;
        else 
        {
            atag[i]=(atag[i]*c)%mod;
            mtag[i]=(mtag[i]*c)%mod;
        }
    }
}
int main()
{
    n=read();blo=sqrt(n);
    for(int i=1;i<=n;i++)v[i]=read();
    for(int i=1;i<=n;i++)bl[i]=(i-1)/blo+1;
    for(int i=1;i<=bl[n];i++)mtag[i]=1;        
    for(int i=1;i<=n;i++)
    {
        int f=read(),a=read(),b=read(),c=read();
        if(f==2)printf("%d\n",(v[b]*mtag[bl[b]]+atag[bl[b]])%mod);
        else solve(f,a,b,c);
    }
    return 0;
}

第八个

click

区间变成问题，对于一个区间，我们维护一个标记，如果一个区间的标记是c，我们之间不查询这一段，直接加上这一段的长度就可以了

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
//by hzw
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 998244353
#define pi acos(-1)
#define inf 0x7fffffff
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,blo;
int v[100005],bl[100005],tag[100005];
void reset(int x)
{
    if(tag[x]==-1)return;
    for(int i=(x-1)*blo+1;i<=blo*x;i++)
        v[i]=tag[x];
    tag[x]=-1;
}
int solve(int a,int b,int c)
{    
    int ans=0;
    reset(bl[a]);
    for(int i=a;i<=min(bl[a]*blo,b);i++)
        if(v[i]!=c)v[i]=c;
        else ans++;
    if(bl[a]!=bl[b])
    {
        reset(bl[b]);
        for(int i=(bl[b]-1)*blo+1;i<=b;i++)
            if(v[i]!=c)v[i]=c;
            else ans++;
    }
    for(int i=bl[a]+1;i<=bl[b]-1;i++)
        if(tag[i]!=-1)
        {
            if(tag[i]!=c)tag[i]=c;
            else ans+=blo;
        }
        else
        {
            for(int j=(i-1)*blo+1;j<=i*blo;j++)
                if(v[j]!=c)v[j]=c;
                else ans++;
            tag[i]=c;
        }    
    return ans;
}
int main()
{
    memset(tag,-1,sizeof(tag));
    n=read();blo=sqrt(n);
    for(int i=1;i<=n;i++)v[i]=read();
    for(int i=1;i<=n;i++)bl[i]=(i-1)/blo+1;
    for(int i=1;i<=n;i++)
    {
        int a=read(),b=read(),c=read();
        printf("%d\n",solve(a,b,c));
    }
    return 0;
}

第九个

click&&click

找众数问题，自古以来众数就是个毒瘤

考虑答案的来源：1.所有完整快的最小众数。2.来自不完整块的某个数

我们可以预先处理好\(i_块\)到\(j_块\)的所有数的最小众数，以便处理第一种情况的时候\(O(1)\)得到

我们定义两个数组：

\(p[i][j]\)：表示\(i_块\)到\(j_块\)的所有数的最小众数

\(s[i][j]\)：类似前缀和，表示前\(i\)个块中\(j\)（离散化）出现了几次

对于\(s\)数组，我们枚举到每一个块的时候，都要从前往后扫一遍，时间复杂度\(O(n\sqrt{n})\)

对于\(p\)数组，我们肯定要枚举\(n^2\),然后在每一个块内，我们都要去判断，所以总复杂度：\(O(\sqrt{n}\sqrt{n}\sqrt{n})\)，总时间复杂度为\(O(n\sqrt{n})\)

考虑\(p, s\)有何用处，对于一个\([l, r]\)，设\(l\)在\(posl\)块中，设\(r\)在\(posr\)块中

此时我们会出现两种情况：

  1. \(posr - posl \leq 1\) 此时暴力修改就可以了，复杂度\(O(\sqrt{n})\)
  2. \(posr - posl \geq 2\)如图：img

红线是\(l\), 蓝线是\(r\)，绿线就是他们之间的块

所以此时的\(ans \in 元素_{yellow} \bigcup 众数_{green}\)

显然，对于绿线中的众数，我们是提前预处理出来的，而对于黄线中每个元素出现的次数就是你左右两边暴力求出来的，加上绿线中这个元素出现的个数

这样的话，对于每次询问，我们就可以在\(O(\sqrt{n})\)的时间内求出答案（不考虑预处理）

我的分析已经超出了LOJ那道题，那道题并没有强制要求在线，莫队就可以完美解决那个问题，更多的分析，是针对蒲公英那道题

一般对于代码，我都会手动格式化，但是hzw的代码，我始终怀着一种敬畏尊重而神圣的感情，我没有修改他的码风

因为我知道他一定会是我的学长

通过学习数列简单分块，我们可以总结出，我们对于一个分块要维护什么：

  1. 不完整的块怎么处理？
  2. 完整的块怎么处理？
  3. 预处理什么？

下面是莫队的相关操蛋操作

给出几个例题

项链

click

莫队入门板子题正解是离线树状数组

小B

click

遇到一个数，先减去他的贡献，在加上他的贡献

小Z

click

埋坑....,我也不知道为什么我的代码能过

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
/*
By TheStars
Time:2020.02.02
*/
#include <bits/stdc++.h>
#define N 500009
using namespace std;
//燕园情 千千结 
int n, m, col[N], ans[N][3], cnt[N];
int fz, fm, block, len;
struct Node {
   int l, r;
   int ord;
}e[N]; 

inline int cmp (Node x, Node y) {
   if (x.l/block == y.l/block) return x.r < y.r;
   return x.l < y.l;
}

inline void add (int x) {
   fz += cnt[x];
   ++ cnt[x];
   fm += len;
   ++ len;
}


inline void del (int x) {
   -- cnt[x];
   fz -= cnt[x];
   -- len;
   fm -= len;
}

inline int gcd (int x, int y) {return !y ? x : gcd(y, x%y);}

int main (){
   int l(1), r(0);
   scanf ("%d%d", &n, &m);
   block = n/sqrt(m);
   for ( int i = 1;i<=n;++i) scanf ("%d", &col[i]);
   for ( int i = 1;i<=m;++i) scanf ("%d%d", &e[i].l, &e[i].r), e[i].ord = i;
   sort (e+1, e+n+1, cmp);
   for ( int i = 1;i<=m;++i) {
      if (e[i].l == e[i].r) {
         ans[e[i].ord][0] = 0;
	 ans[e[i].ord][1] = 1;
	 continue;
      }
      while (l > e[i].l) add (col[--l]);
      while (r > e[i].r) del (col[r--]);
      while (l < e[i].l) del (col[l++]);
      while (r < e[i].r) add (col[++r]);
      int g = gcd(fz, fm);
      ans[e[i].ord][0] = fz/g;
      ans[e[i].ord][1] = fm/g;
   }
   for ( int i = 1;i<=m;++i) cout << ans[i][0] << '/' << ans[i][1] << '\n';
   return 0;
}

待修改莫队

click

正常莫队都是离线的，不支持修改，对于这种待修改的，我们需要在原来\(l, r\)的基础上加上一维\(t\)

称为时间戳，查询操作的时间戳，沿用最近一次修改的时间戳

跑主算法时定义当前时间戳为\(t\)，对于每个查询操作，如果当前时间戳相对太大了，说明已进行的修改操作比要求的多，就把之前改的改回来，反之往后改。

只有当当前区间和查询区间左右端点、时间戳均重合时，才认定区间完全重合，此时的答案才是本次查询的最终答案。

通俗地讲，就是再弄一指针，在修改操作上跳来跳去，如果当前修改多了就改回来，改少了就改过去，直到次数恰当为止。

这样，我们当前区间的移动方向从四个（\([l−1,r]、[l+1,r]、[l,r−1]、[l,r+1]\)）

变成了六个（\([l−1,r,t]、[l+1,r,t]、[l,r−1,t]、[l,r+1,t]、[l,r,t−1]、[l,r,t+1]\)）

嫖了一份代码：

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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 50500
#define maxc 1001000
int a[maxn], cnt[maxc], ans[maxn], belong[maxn];
struct query {
	int l, r, time, id;
} q[maxn];
struct modify {
	int pos, color, last;
} c[maxn];
int cntq, cntc, n, m, size, bnum;
int cmp(query a, query b) {
   return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.r] ^ belong[b.r]) ? belong[a.r] < belong[b.r] : a.time < b.time);
}
#define isdigit(x) ((x) >= '0' && (x) <= '9')
inline int read() {
   int res = 0;
   char c = getchar();
   while(!isdigit(c)) c = getchar();
   while(isdigit(c)) res = (res << 1) + (res << 3) + (c ^ 48), c = getchar();
   return res;
}
int main() {
   n = read(), m = read();
   size = pow(n, 2.0 / 3.0);
   bnum = ceil((double)n / size);
   for(int i = 1; i <= bnum; ++i) 
      for(int j = (i - 1) * size + 1; j <= i * size; ++j) belong[j] = i;
	 for(int i = 1; i <= n; ++i) 
	    a[i] = read();
   for(int i = 1; i <= m; ++i) {
      char opt[100];
      scanf("%s", opt);
      if(opt[0] == 'Q') {
         q[++cntq].l = read();
	 q[cntq].r = read();
	 q[cntq].time = cntc;
	 q[cntq].id = cntq;
      }
      else if(opt[0] == 'R') {
         c[++cntc].pos = read();
	 c[cntc].color = read();
      }
   }
   sort(q + 1, q + cntq + 1, cmp);
   int l = 1, r = 0, time = 0, now = 0;
   for(int i = 1; i <= cntq; ++i) {
      int ql = q[i].l, qr = q[i].r, qt = q[i].time;
      while(l < ql) now -= !--cnt[a[l++]];
      while(l > ql) now += !cnt[a[--l]]++;
      while(r < qr) now += !cnt[a[++r]]++;
      while(r > qr) now -= !--cnt[a[r--]];
      while(time < qt) {
	 ++time;
	 if(ql <= c[time].pos && c[time].pos <= qr) now -= !--cnt[a[c[time].pos]] - !cnt[c[time].color]++;
	    swap(a[c[time].pos], c[time].color);
      }
      while(time > qt) {
	 if(ql <= c[time].pos && c[time].pos <= qr) now -= !--cnt[a[c[time].pos]] - !cnt[c[time].color]++;
	    swap(a[c[time].pos], c[time].color);
	    --time;
      }
      ans[q[i].id] = now;
   }
   for(int i = 1; i <= cntq; ++i) 
      printf("%d\n", ans[i]);
   return 0;
}

#晚上

写博客 补坑