12 条题解

  • 1
    @ 2023-11-18 19:37:17

    #include <iostream> using namespace std; int a[1000005], s[1000005], cf[1000005], n, m, k, l, r, c; int main() { cin >> n >> m >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; cf[i] = a[i] - a[i - 1]; } for (int i = 1; i <= m; i++) { cin >> l >> r >> c; cf[l] += c; cf[r + 1] -= c; } for (int i = 1; i <= n; i++) { a[i] = a[i - 1] + cf[i]; } for (int i = 1; i <= n; i++) { s[i] = s[i - 1] + a[i]; } for (int i = 1; i <= k; i++) { cin >> l >> r; cout << s[r] - s[l - 1] << endl; } return 0; }

    • 1
      @ 2023-11-15 18:04:14

      #include <queue> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> using namespace std; #define LL long long const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; int a[N]; int ans[N]; int main() { int n , m , k; cin >> n >> m >> k; for(int i = 1 ; i <= n ; i++) { cin >> a[i]; ans[i] = a[i] - a[i-1]; }

      while(m--)
{
	int l,r,num;
	cin >> l >> r >> num;
	ans[l]+= num;
	ans[r+1] -= num;
}
for(int i = 1 ; i <= n ; i++)
	ans[i] += ans[i-1];
for(int i = 1 ; i <= n ; i++)
	ans[i] += ans[i-1];
while(k--)
{
	int l , r;
	cin >> l >> r;
	cout << ans[r] - ans[l-1] << endl;
}
return 0;

      }

      • 1
        @ 2023-11-8 19:59:56 
        #include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int a[N];
int ans[N];
int main()
{
	int n , m , k;
	cin >> n >> m >> k;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> a[i];
		ans[i] = a[i] - a[i-1];
	}
	

	while(m--)
	{
		int l,r,num;
		cin >> l >> r >> num;
		ans[l]+= num;
		ans[r+1] -= num;
	}
	for(int i = 1 ; i <= n ; i++)
		ans[i] += ans[i-1];
	for(int i = 1 ; i <= n ; i++)
		ans[i] += ans[i-1];
	while(k--)
	{
		int l , r;
		cin >> l >> r;
		cout << ans[r] - ans[l-1] << endl;
	}
	return 0; 
}
        • 1
          @ 2023-5-31 20:20:12

          #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<iomanip> #include<algorithm> #include<string> #include<stack> using namespace std; const int N=1e6+10; const int INF=0x3f3f3f3f; int n,m,k,a[N],s[N],cf[N],l,r,c; int main(){ cin>>n>>m>>k; for(int i=1;i<=n;i++){ cin>>a[i]; cf[i]=a[i]-a[i-1]; } while(m--){ cin>>l>>r>>c; cf[l]+=c; cf[r+1]-=c; } for(int i=1;i<=n;i++){ a[i]=a[i-1]+cf[i]; } for(int i=1;i<=n;i++){ s[i]=s[i-1]+a[i]; } while(k--){ cin>>l>>r; cout<<s[r]-s[l-1]<<endl; } return 0; }

          • 1
            @ 2023-4-30 15:43:28 
            #include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int a[N],ans[N], l,r,c;
int main(){
	int n,m,k;
	cin >> n >> m >>k;
	for (int i=1; i<=n; i++){
		cin >> a[i];
		ans[i]=a[i]-a[i-1];
	}
	while(m--){
		
		cin >>l >>r >>c;
		ans[l]+=c;
		ans[r+1]-=c;
	}
	
	for (int i=1; i<=n; i++){
		ans[i]+=ans[i-1];
	}
	for (int i=1; i<=n; i++){
		ans[i]+=ans[i-1];
	}
	while(k--){
		
		cin >> l >> r;
		cout << ans[r]-ans[l-1] << endl;
	} 
	
	return 0;
}
            • 1
              @ 2023-3-12 15:43:42 
              /*********************************

*********************************/
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],f[1000005],k,l,r,x;
int main()
{    
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
    	cin>>a[i];
	}
	while(m--) {
		cin>>l>>r>>x;
		f[l]+=x;
		f[r+1]-=x;
	}
	for(int i=1;i<=n;i++) {
		f[i]+=f[i-1];
//		cout<<f[i]<<" ";
	}
//	puts("");
	for(int i=1;i<=n;i++) {
		f[i]+=a[i];
//		cout<<f[i]<<" ";
	}
//	puts("");
for(int i=1;i<=n;i++) {
		f[i]+=f[i-1];
//		cout<<f[i]<<" ";
	}
//	puts("");
	while(k--) {
		cin>>l>>r;
		cout<<f[r]-f[l-1]<<"\n";
	}
    return 0;
}
/*
1 2 3 4 5
0 0 0 0 0
1 0 -1 0 0
1 0 1 0 -2
2 3 4 5 5
*/
              • 1
                @ 2021-12-18 20:03:13 
                /*****************************************

******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int a[N];
int ans[N];
int main()
{
	int n , m , k;
	cin >> n >> m >> k;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> a[i];
		ans[i] = a[i] - a[i-1];
	}
	

	while(m--)
	{
		int l,r,num;
		cin >> l >> r >> num;
		ans[l]+= num;
		ans[r+1] -= num;
	}
	for(int i = 1 ; i <= n ; i++)
		ans[i] += ans[i-1];
	for(int i = 1 ; i <= n ; i++)
		ans[i] += ans[i-1];
	while(k--)
	{
		int l , r;
		cin >> l >> r;
		cout << ans[r] - ans[l-1] << endl;
	}
	return 0; 
}
                • 0
                  @ 2024-7-24 10:47:58

                  #include<bits/stdc++.h>

                  //#define int long long

                  using namespace std;

                  const int N = 1e6 +10;

                  const int INF=0x3f3f3f;

                  int n,m,z,l,r,c,a[N],b[N],d[N];

                  int main(){

                  cin>>n>>m>>z;

for(int i = 1;i<=n;i++){

    cin>>a[i];

    b[i] = a[i]- a[i-1];

                  }

                  for(int i = 1;i<=m;i++){

    cin>>l>>r>>c;

    b[l]+=c;

    b[r+1]-=c;

                  }

                  for(int i = 1;i<=n;i++){

    a[i] = b[i]+a[i-1];

    d[i] = d[i-1]+a[i];

                  }

                  while(z--){

    cin>>l>>r;

    cout<<d[r]-d[l-1]<<endl;

}

return 0;

                  }

                  • 0
                    @ 2023-11-15 18:34:14

                    #include<bits/stdc++.h>

                    using namespace std;

                    const int N = 1e6 + 10;

                    const int INF = 0x3f3f3f3f;

                    int a[N]; int ans[N]; int main() { int n , m , k; cin >> n >> m >> k; for(int i = 1 ; i <= n ; i++) { cin >> a[i]; ans[i] = a[i] - a[i-1]; }

                    while(m--)
{
	int l,r,num;
	cin >> l >> r >> num;
	ans[l]+= num;
	ans[r+1] -= num;
}
for(int i = 1 ; i <= n ; i++)
	ans[i] += ans[i-1];
for(int i = 1 ; i <= n ; i++)
	ans[i] += ans[i-1];
while(k--)
{
	int l , r;
	cin >> l >> r;
	cout << ans[r] - ans[l-1] << endl;
}
return 0;

                    }

                    • 0
                      @ 2023-9-12 12:07:20

                      hahahaha

                      • -3
                        @ 2021-11-20 17:01:19 
                        #include<iostream>
using namespace std;
int n,m,k,acc[1000006],cf[1000006],l,r,c,qz[1000006];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&acc[i]);
		cf[i]=acc[i]-acc[i-1];
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&l,&r,&c);
		cf[l]+=c;
		cf[r+1]-=c;
	}
	for(int i=1;i<=n;i++)
	{
		acc[i]=cf[i]+acc[i-1];
	}
	for(int i=1;i<=n;i++)
	{
		qz[i]=acc[i]+qz[i-1];
	}
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d",&l,&r);
		printf("%d\n",qz[r]-qz[l-1]);
	}
	
	return 0;
}
                        • -4
                          @ 2022-9-26 16:35:30

                          #include<iostream> using namespace std; int n,m,k,l,r,c,a[1000005],b[1000005]; int main(){ cin>>n>>m>>k; for(int i=1;i<=n;i++){ cin>>a[i]; b[i]=a[i]-a[i-1]; //构造差分数组 } for(int i=1;i<=m;i++){ cin>>l>>r>>c; b[l]+=c; b[r+1]-=c; } for(int i=1;i<=n;i++){ a[i]=b[i]+a[i-1]; //恢复原数组（加数后） b[i]=a[i]+b[i-1]; //构造前缀和数组 } for(int i=1;i<=k;i++){ cin>>l>>r; cout<<b[r]-b[l-1]<<endl;// 应用前缀和 } }

                          • 1

                          差分数组模板

                          信息

                          ID
                          1282
                          时间
                          1000ms
                          内存
                          256MiB
                          难度
                          6
                          标签
                          递交数
                          555
                          已通过
                          187
                          上传者
                          1. 关于
                          2. 联系我们
                          3. 隐私
                          4. 服务条款
                          5. 版权申诉
                          6. Language
                          7. Theme
                          3. Worker 0 in 26ms
                          4. Powered by Hydro v3.15.13 Community