上次做过类似的题，原来这道还要简单些？？
上次那道题是每天可以同时买进卖出，所以用两个优先队列，一个存买进，一个存卖出（供反悔的队列）。
这道题实际上用一个就够了？？？但是不好理解！！
所以我还是用了俩...
和之前那道题不同的是，如果我选择了反悔，之前第二个队列的队头就完全没有用了，但是我们可以选择重新买它，所以把它重新放到第一个队列。
#include<bits/stdc++.h> using namespace std; priority_queue < int, vector < int >, greater < int > > q1, q2; int n, a[100005]; long long ans; int main() { freopen("trade.in", "r", stdin); freopen("trade.out", "w", stdout); scanf("%d", &n); for(int i = 1; i <= n; i ++) scanf("%d", &a[i]); for(int i = 1; i <= n; i ++) { int x1, x2, r1 = 0, r2 = 0; if(!q1.empty()) { x1 = q1.top(); if(a[i] - x1 > 0) r1 = a[i] - x1; } if(!q2.empty()) { x2 = q2.top(); if(a[i] - x2 > 0) r2 = a[i] - x2; } if(r1 >= r2 && r1) { q1.pop(); q2.push(a[i]); ans += r1; } else if(r2 > r1 && r2 ) { q2.pop(); q2.push(a[i]); q1.push(x2); ans += r2; } else q1.push(a[i]); } printf("%lld", ans); return 0; }
这道题乍一看是推公式$O(1)$的数论？？经$yuli$dalao考场上一个多小时的测试发现没有这样的式子....
所以$zc$dalao通过研究打表发现了正解！其实是莫队！
？？？
首先我们也来打一下表....发现了两个递推式：$S_n^m=S_n^{m-1}+C_n^m$和$S_n^m=2S_{n-1}^m-C_{n-1}^m$，我们可以把$[n,m]$看成一个区间来进行离线莫队转移，复杂度$O(nsqrt{n})$。
#include<bits/stdc++.h> #define mod 1000000007 #define LL long long using namespace std; int blo[100005]; struct Node { int n, m, id; } qus[100005]; bool cmp(Node a, Node b) { if(blo[a.m] == blo[b.m]) return a.n < b.n; return a.m < b.m; } LL fac[100005], inv[100005]; LL C(int n, int m) { if(m > n) return 0; return fac[n] * inv[m] % mod * inv[n - m] % mod; } LL mpow(LL a, LL b) { LL ans = 1; for(; b; b >>= 1, a = a * a % mod) if(b & 1) ans = ans * a % mod; return ans; } void init() { fac[0] = 1; inv[0] = 1, inv[1] = 1; for(int i = 1; i <= 100005; i ++) fac[i] = fac[i - 1] * i % mod; for(int i = 2; i <= 100005; i ++) inv[i] = mpow(fac[i], mod - 2); for(int i = 1; i <= 100005; i ++) blo[i] = i/300 + 1; } int Ans[100005]; int main() { freopen("sum.in", "r", stdin); freopen("sum.out", "w", stdout); int id; scanf("%d", &id); init(); int T; scanf("%d", &T); for(int i = 1; i <= T; i ++) scanf("%d%d", &qus[i].n, &qus[i].m), qus[i].id = i; sort(qus + 1, qus + 1 + T, cmp); int n = qus[1].n, m = qus[1].m; LL ans = 0; for(int i = 0; i <= m; i ++) ans = (ans + C(n, i)) % mod; Ans[qus[1].id] = ans; for(int i = 2; i <= T; i ++) { while(qus[i].m < m) { ans = (ans - C(n, m) + mod) % mod; m --; } while(qus[i].n > n) { ans = (2LL * ans % mod - C(n, m) + mod) % mod; n ++; } while(qus[i].m > m) { m ++; ans = (ans + C(n, m)) % mod; } while(qus[i].n < n) { n --; ans = 1LL * (ans + C(n, m)) * inv[2] % mod; } Ans[qus[i].id] = ans; } for(int i = 1; i <= T; i ++) printf("%d ", Ans[i]); return 0; }
感觉这种题就算让我再做一次，也写不出来...重载什么的简直太难记了aaa！！
对于第一个询问，直接分别处理每行和每列就行了，每行就直接加，每列用差分处理。
如何查找联通块数量？
分别处理两种情况：
1）与下边相交
对于上面的矩形，查找它下一排最后一个与它相交的矩形，向前枚举直到不相交，把相交的矩形连边。
2）与右边相交
对于左边的矩形，查找它右边与它相交的所有矩形，连边。
以上操作用二分实现。注意的是，因为我们建边是在每排的基础上（因为查询的是排），所以第一种应该建在下面那排，第二种应该建在两个矩形上边界的排取max。（查询前缀时才能保证合法）
stl（vector简直tql！QAQ）
#include<bits/stdc++.h> #define LL long long using namespace std; int ans2[100005]; LL ans1[100005], sum2[100005], sum1[100005]; struct Data { int lx, ly, rx, ry; Data(int lx = 0, int ly = 0, int rx = 0, int ry = 0) : lx(lx), ly(ly), rx(rx), ry(ry) { } } A[100005]; struct Node { int id, l, r; Node(int id = 0, int l = 0, int r = 0) : id(id), l(l), r(r) { } }; vector < Node > row[100005], col[100005]; bool operator < (const Node &a, const Node &b) { return a.l < b.l || (a.l == b.l && a.r < b.r); } vector < pair < int , int > > G[1000005]; int root[100005], edge, num; int find(int x) { if(root[x] != x) root[x] = find(root[x]); return root[x]; } void merge(int x, int y) { x = find(x); y = find(y); if(x != y) root[x] = y, ++ edge; } int main() { freopen("building.in", "r", stdin); freopen("building.out", "w", stdout); int opt; scanf("%d", &opt); int n, m, k, p; scanf("%d%d%d%d", &n, &m, &k, &p); for(int i = 1; i <= k; i ++) { int lx, ly, rx, ry; scanf("%d%d%d%d", &lx, &ly, &rx, &ry); A[i] = Data(lx, ly, rx, ry); row[lx].push_back(Node(i, ly, ry)); col[ly].push_back(Node(i, lx, rx)); if(lx == rx) sum1[lx] += (ry - ly + 1); else sum2[lx] ++, sum2[rx + 1] --; } for(int i = 1; i <= n; i ++) sort(row[i].begin(), row[i].end()); for(int i = 1; i <= m; i ++) sort(col[i].begin(), col[i].end()); for(int i = 1; i <= k; i ++) { int down = A[i].rx + 1; if(down <= n && row[down].size()) { int p = upper_bound(row[down].begin(), row[down].end(), Node(0, A[i].ry, m + 1)) - row[down].begin() - 1; for(; p >= 0 && row[down][p].r >= A[i].ly; p --) G[down].push_back(make_pair(i, row[down][p].id)); } int right = A[i].ry + 1; if(right <= m && col[right].size()) { if(right < 0) return 0; int p = upper_bound(col[right].begin(), col[right].end(), Node(0, A[i].rx, n + 1)) - col[right].begin() - 1; for(; p >= 0 && col[right][p].r >= A[i].lx; p --) G[max(A[i].lx, A[col[right][p].id].lx)].push_back(make_pair(i, col[right][p].id)); } } for(int i = 1; i <= n; i ++) sum2[i] += sum2[i-1]; for(int i = 1; i <= n; i ++) { sum2[i] += sum2[i-1]; sum1[i] += sum1[i-1]; ans1[i] = sum1[i] + sum2[i]; } for(int i = 1; i <= k; i ++) root[i] = i; for(int i = 1; i <= n; i ++) { num += row[i].size(); for(int j = 0; j < G[i].size(); j ++) merge(G[i][j].first, G[i][j].second); ans2[i] = num - edge; } while(p --) { int u, v; scanf("%d%d", &u, &v); if(u) printf("%d ", ans2[v]); else printf("%lld ", ans1[v]); } return 0; }