思维题——倒序差分的运用
题目描述
筱玛是一个热爱线段树的好筱玛。
筱玛的爷爷马爷在游戏中被筱玛吊打了，于是他恼羞成怒，决定给筱玛出这样一道数据结构题：
给定一个长度为 nn的数组AA，刚开始每一项的值均为00。
支持以下两种操作，操作共 mm次：
1 l r1 l r：将Al∼ArAl∼Ar的每一项的值加上11。
2 l r2 l r：执行操作编号在[l,r][l,r]内的所有操作各一次，保证rr小于当前操作的编号。
mm次操作结束后，你要告诉马爷AA数组变成什么样子了。
由于答案可能会很大，你只需要输出数组 AA中的每个数在模109+7109+7意义下的值。
输入描述:
第一行两个数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; }
