这题如果数据范围大怎么用前缀和写

lsmCC

https://www.luogu.com.cn/problem/AT_abc318_b   怎么用前缀和写

1. //如果数据范围大，就要用前缀和去写
   
2. #include <bits/stdc++.h>
   
3. using namespace std;
   
4. const int N=103;
   
5. int g[N][N];
   
6. typedef long long ll;
   
7. int main()
   
8. {
   
9.     int n;
   
10.     cin>>n;
    
11.     int a,b,c,d;
    
12.     for(int i=1;i<=n;i++)
    
13.     {
    
14.         cin>>a>>b>>c>>d;
    
15.         for(int i=a;i<b;i++)
    
16.         {
    
17.             for(int j=c;j<d;j++)
    
18.             {
    
19.                 g[i][j]++;
    
20.             }
    
21.         }
    
22.         
    
23.     }
    
24.     //其他的应该都为0，如果不为0，则说明被覆盖了
    
25.     ll ans=0;
    
26. 
    
27.     for(int i=1;i<=N;i++)
    
28.     {
    
29.         for(int j=1;i<=N;i++)
    
30.         {
    
31.             g[i][j]+=g[i-1][j]+g[i][j-1]+g[i][j];
    
32.             if(g[i][j])
    
33.            {
    
34.             ans++;
    
35. 
    
36.            }
    
37.         }
    
38.         
    
39.     }
    
40.     cout<<ans<<endl;
    
41. }

复制代码

自己写的，感觉没有理解前缀和在这题应该怎么用

Mike_python小

看起来你对前缀和的理解还有些混淆。让我来帮你分析一下你给出的代码，并解释一下正确的前缀和的用法。

首先，让我们来分析你给出的代码中的问题：

1. 在计算前缀和时，你使用了一个二重循环来更新 g[i][j] 的值，但是这样的更新方式并不符合前缀和的定义。正确的前缀和更新应该是累加之前的结果，而不是简单地累加当前元素的值。
2. 在遍历计算被覆盖的格子数量时，你有一个嵌套的循环，但是你的内层循环条件写成了 i<=N 而不是 j<=N。
3. 在输出结果时，你使用了 ll 类型来保存结果，这是正确的，但是在计算前缀和时，也应该使用 ll 类型来避免溢出。

接下来，让我给出一份修改后的代码示例，以帮助你更好地理解如何使用前缀和来解决这个问题：

2. #include <bits/stdc++.h>
3. using namespace std;
5. const int N = 103;
6. int g[N][N];
8. int main() {
9.     int n;
10.     cin >> n;
11.     int a, b, c, d;
12.     for (int i = 1; i <= n; i++) {
13.         cin >> a >> b >> c >> d;
14.         for (int x = a; x < b; x++) {
15.             for (int y = c; y < d; y++) {
16.                 g[x][y]++;
17.             }
18.         }
19.     }
21.     // 计算前缀和
22.     long long ans = 0;
23.     for (int i = 1; i < N; i++) {
24.         for (int j = 1; j < N; j++) {
25.             g[i][j] += g[i-1][j] + g[i][j-1] - g[i-1][j-1];
26.             if (g[i][j]) {
27.                 ans++;
28.             }
29.         }
30.     }
32.     cout << ans << endl;
34.     return 0;
35. }

复制代码

在这段代码中，我们首先按照你给出的方式读入数据，然后计算前缀和的部分进行了修改。我们使用了两重循环来更新 g[i][j] 的值，同时使用 long long 类型来保存结果以避免溢出。

希望这次能够帮到你！如果还有其他问题，请随时提问。

isdkz

你的代码中存在一些小错误，我来帮你修改一下：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int N=103;
   
4. int g[N][N];
   
5. typedef long long ll;
   
6. int main()
   
7. {
   
8.     int n;
   
9.     cin>>n;
   
10.     int a,b,c,d;
    
11.     for(int i=1;i<=n;i++)
    
12.     {
    
13.         cin>>a>>b>>c>>d;
    
14.         for(int i=a;i<b;i++)
    
15.         {
    
16.             for(int j=c;j<d;j++)
    
17.             {
    
18.                 g[ i][j]++;
    
19.             }
    
20.         }
    
21.         
    
22.     }
    
23.     //其他的应该都为0，如果不为0，则说明被覆盖了
    
24.     ll ans=0;
    
25. 
    
26.     for(int i=1;i<N;i++) // 修改这里，从1开始
    
27.     {
    
28.         for(int j=1;j<N;j++) // 修改这里，从1开始
    
29.         {
    
30.             g[ i][j]+=g[i-1][j]+g[ i][j-1]-g[i-1][j-1]; // 修改这里
    
31.             if(g[ i][j]>0) // 修改这里
    
32.             {
    
33.                 ans++;
    
34.             }
    
35.         }
    
36.         
    
37.     }
    
38.     cout<<ans<<endl;
    
39. }
    

复制代码

在修改后的代码中，我更正了两处错误：

1. 在计算前缀和时，需要注意数组下标从1开始，所以修改了两处循环的起始值。
2. 在计算前缀和时，需要使用 g[ i][j]+=g[i-1][j]+g[ i][j-1]-g[i-1][j-1] 来更新前缀和数组 g。

希望这个修改后的代码能够帮助你理解如何正确地使用前缀和来解决这个问题。

额外减小

前缀和不是处理区间的和吗？看不出这个跟前缀和有什么关系。

zhangjinxuan

先二维差分，然后二维前缀和。运用了容斥原理。

1. //如果数据范围大，就要用前缀和去写
   
2. #include <bits/stdc++.h>
   
3. using namespace std;
   
4. const int N=103;
   
5. int g[N][N];
   
6. typedef long long ll;
   
7. int main()
   
8. {
   
9.     int n;
   
10.     cin>>n;
    
11.     int a,b,c,d;
    
12.     for(int i=1;i<=n;i++)
    
13.     {
    
14.         cin>>a>>b>>c>>d;
    
15.                 ++a,++b,++c,++d; //整体平移，方便边界处理
    
16. //        for(int i=a;i<b;i++)
    
17. //        {
    
18. //            for(int j=c;j<d;j++)
    
19. //            {
    
20. //                g[i][j]++;
    
21. //            }
    
22. //        }
    
23.         g[a][c]++; // 二维差分
    
24.         g[a][d]--;
    
25.         g[b][c]--;
    
26.         g[b][d]++;
    
27.         
    
28.     }
    
29.     //其他的应该都为0，如果不为0，则说明被覆盖了
    
30.     ll ans=0;
    
31. 
    
32.     for(int i=1;i<N;i++)
    
33.     {
    
34.         for(int j=1;j<N;j++) //注意循环变量
    
35.         {
    
36. //            g[i][j]+=g[i-1][j]+g[i][j-1]+g[i][j];
    
37.             g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1]; //容斥
    
38.             if(g[i][j])
    
39.            {
    
40.             ans++;
    
41. 
    
42.            }
    
43.         }
    
44.         
    
45.     }
    
46.     cout<<ans<<endl;
    
47. }

复制代码

https://www.luogu.com.cn/record/146848699

听你这么说感觉你对二维的前缀和很疑惑，可以学一下容斥，再来学一下二维前缀和与差分。