第一行两个数n,mn,m，分别表示数组长度及操作次数。
接下来mm行，每行三个数opt,l,ropt,l,r，表示一次操作。
输出一行共nn个数，表示mm次操作结束后，A1∼AnA1∼An的值。
对于100%的数据，1≤n≤105,1≤m≤1051≤n≤105,1≤m≤105。
//#pragma comment(linker, "/STACK:1024000000,1024000000") //#pragma GCC optimize(2) //#include <bits/stdc++.h> #include <algorithm> #include <iostream> #include<sstream> #include<iterator> #include<cstring> #include<string> #include<cstdio> #include<cctype> #include<vector> #include<deque> #include<queue> #include<stack> #include<map> #include<list> #include<set> using namespace std; typedef double dou; typedef long long ll; typedef pair<int, int> pii; #define pai acos(-1.0) #define M 200005 #define inf 1e18 #define mod 1000000007 #define left k<<1 #define right k<<1|1 #define W(a) while(a) #define ms(a,b) memset(a,b,sizeof(a)) struct Data { ll Opt, L, R; }num[M];//操作 ll n, m, pos, pre; ll ans[M], cnt[M];//ans为差分序列，cnt为操作次数 void init() { ms(cnt, 0); ms(ans, 0); pos = pre = 0; cnt[m] = 1;//我们知道最后一次操作的次数肯定为一次 } int main() { ios::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> num[i].Opt >> num[i].L >> num[i].R;//保存好操作 } init(); for (int i = m; i >= 1; i--) { pos += cnt[i];//差分得到操作次数 pos = (pos + mod) % mod; if (num[i].Opt == 1) { ans[num[i].L] += pos; ans[num[i].R + 1] -= pos; } else { cnt[num[i].R] += pos; cnt[num[i].L - 1] -= pos; } } for (int i = 1; i <= n; i++) { pre += ans[i]; cout << (pre + mod) % mod<<‘ ‘ ; } return 0; }
原文：https://www.cnblogs.com/caibingxu/p/11141365.html