题目描述
思路&&感想
这题其实就是一维差分的一道裸题，一开始竟然没看出来，写了个O(n^2)的算法居然还过了？
赛后看大佬的题解才想到是差分（还是练太少）
差分模板
#include<iostream> using namespace std; const int N=100010; int n,m; int a[N],b[N]; void insert(int l,int r,int c) { b[l]+=c; b[r+1]-=c; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) insert(i,i,a[i]); while(m--) { int l,r,c; scanf("%d%d%d",&l,&r,&c); insert(l,r,c); } for(int i=1;i<=n;i++) b[i]+=b[i-1]; for(int i=1;i<=n;i++) printf("%d ",b[i]); return 0; }
AC代码
int oddnumber(int n, int m, vector<int>& l, vector<int>& r) { int a[500050],ans=0; a[1]=m; for(int i=0;i<m;i++) { a[l[i]]++; a[r[i]+1]--; } for(int i=1;i<=n;i++) a[i]+=a[i-1]; for(int i=1;i<=n;i++) { if(a[i]%2==1) ans++; } return ans; }