网站建设详细流程视频,最新在线免费网站,宜宾团购网站建设,莱芜网站建设公司因为只有std#xff0c;没有自我实现#xff0c;所以是无码专区
主要是为了训练思维能力
my idea顾名思义#xff0c;记录了我的整个思维过程#xff0c;以及自己部分实现细节口胡#xff0c;还有期望分数
solution才是dls正解#xff0c;但是因为只有潦草几句#x…因为只有std没有自我实现所以是无码专区
主要是为了训练思维能力
my idea顾名思义记录了我的整个思维过程以及自己部分实现细节口胡还有期望分数
solution才是dls正解但是因为只有潦草几句所以大部分会有我自己基于正解上面的算法实现过程可能选择的算法跟std中dls的实现不太一样。
std可能也会带有博主自己的注释。 problem
有 nnn 个数其表示为 2ai⋅3bi2^{a_i}·3^{b_i}2ai⋅3bi给定 ai,bia_i,b_iai,bi。
对于所有的非空子集求出它们的最小公倍数并求和。
答案对 1e971e971e97 取模。
测试点编号n≤n\len≤ai,bi≤a_i,b_i\leai,bi≤1−21-21−220202010910^91093−43-43−410310^310310910^91095−65-65−610510^510510310^31037−107-107−1010510^510510910^9109my idea
读完题就直接思考具有特殊性质的数据点因为往往这种数据点的算法就是正解最朴素的原始样子。有价值的题都会这么设计部分分。某些毒瘤题呃呃呃
n≤103n\le 10^3n≤103 应该是与 n2n^2n2 挂钩的算法。
大概是枚举子集的最小值和最大值强制入选然后二维数点中间所有可以选择的数。为了避免算重相同值的点还得强制规定一个大小比如编号。
ai,bi≤103a_i,b_i\le 10^3ai,bi≤103 本质上与上面差不多。
只不过是从因子的幂次角度入手枚举。
枚举最大值的 a,ba,ba,b二维数点所有 ai≤a,bi≤ba_i\le a,b_i\le bai≤a,bi≤b 的点考虑是否选择。
同样为了避免算重也得规定第三排序法则。
以上只是粗略的想法并未细想。因为这个时候发现上面的做法其实是可以做正解的。
2a,3b2^a,3^b2a,3b 是相互独立的可分开计算。
将所有数按 aaa 幂次大小升序排序后。
考虑枚举第 iii 个数的 aaa 作为最小公倍数的 aaa。
显然子集内的其余元素只能从 1≤ji1\le ji1≤ji 里面选。
对 bbb 建立权值线段树维护元素个数。
为了去重强制枚举的数必选那么最小公倍数 bbb 的至少是 bib_ibi。
直接线段树上查一段区间作为作为最小公倍数 bbb 的答案。
具体而言
线段树的叶子节点 xxx 维护的是 bj≤x,1≤jib_j\le x,1\le jibj≤x,1≤ji 的 jjj 的个数假设为 ccc 个。
一个叶子节点如果是最后选的子集数的最小公倍数的 bbb 的话。
那么可能的子集为 2c−12^{c-1}2c−1 个−1-1−1 是因为必须要求 bjxb_jxbjx 的 jjj 中强制被选一个这样才会有 bjb_jbj否则会假掉。
一个点对答案的贡献就是 2c−1∗x2^{c-1}*x2c−1∗x此时必须保证有至少一个 bjxb_jxbjx 才行。
所以一个点还要维护一个标记 fff表示是否有至少一个 jjj 满足 bjxb_jxbjx。
那么一个点对答案的贡献应该是 2c−1∗x∗f2^{c-1}*x*f2c−1∗x∗f。
对于枚举的 iii 而言算出来的贡献为 2ai∗2^{a_i}*2ai∗ 线段树查询区间 [bj,MaxB][b_j,MaxB][bj,MaxB]。
注意到这个形式意味着还要对 bbb 进行离散化处理。
因为 iii 能让 bib_ibi 的线段树对应节点 f1f1f1而这之前可能是 f0f0f0。
所以要先修改再查询。
修改根据节点维护信息对应的应是区间修改 [1,bi][1,b_i][1,bi]且特殊的 bib_ibi 的 fff 要置为 111。
所以可以拆成区间修改 [1,bi)[1,b_i)[1,bi) 和单点修改 bib_ibi。
懒标记一旦增加相当于是多了一个个数幂次 111拆出来变成外部 ×2\times 2×2。
即 2lazy⋅(2c1∗x1∗f12c2∗x2∗f2...)2^{lazy}·(2^{c_1}*x_1*f_12^{c_2}*x_2*f_2...)2lazy⋅(2c1∗x1∗f12c2∗x2∗f2...)。
时间复杂度为 O(nlogn)O(n\log n)O(nlogn)。 solution
首先不妨设 ai,bia_i,b_iai,bi 两两不同。
考虑枚举集合中 bib_ibi 最大的元素将所有 bjbib_jb_ibjbi 的元素按 aja_jaj 从小到大排序。
不妨记作 a1′,a2′,...,ai−1′a_1,a_2,...,a_{i-1}a1′,a2′,...,ai−1′那么会有 2i−12^{i-1}2i−1 个子集最大值是 ai−1′a_{i-1}ai−1′。
考虑将 aia_iai 加入后所有最大值 aia_iai 的子集最大值都变成了 aia_iai剩下的子集不变。
将 aia_iai 加入到上面的有序序列后所有比 aia_iai 大的元素排名都会 111对应的子集个数会翻倍。
问题等价于区间乘 222 以及区间求和线段树维护。
就是my idea类似的思想yeah我做出来了 std
#include bits/stdc.h
#define ls(x) (x 1)
#define rs(x) ((x 1) | 1)
#define LL long long
using namespace std;
const int maxn 100010;
const LL mod 1000000007;struct node {int x, y, rank;
};bool cmp1(node x, node y) {return x.x y.x ? x.y y.y : x.x y.x;
}bool cmp2(node x, node y) {return x.y y.y ? x.x y.x : x.y y.y;
}
node a[maxn];struct SegementTree {LL sum, cnt, lz;
};
SegementTree tr[maxn * 4];LL qpow(LL x, LL y) {LL ans 1;for (; y; y 1) {if (y 1)ans (ans * x) % mod;x (x * x) % mod;}return ans;
}void pushup(int x) {tr[x].sum (tr[ls(x)].sum tr[rs(x)].sum) % mod;tr[x].cnt (tr[ls(x)].cnt tr[rs(x)].cnt) % mod;
}void maintain(int x, int y) {tr[x].sum (tr[x].sum * qpow(2, y)) % mod;tr[x].lz y;
}void pushdown(int x) {if (tr[x].lz) {if (tr[ls(x)].cnt)maintain(ls(x), tr[x].lz);if (tr[rs(x)].cnt)maintain(rs(x), tr[x].lz);tr[x].lz 0;}
}void build(int x, int l, int r) {if (l r) {tr[x].sum tr[x].cnt 0;return;}int mid (l r) 1;build(ls(x), l, mid);build(rs(x), mid 1, r);pushup(x);
}void update_cnt(int x, int l, int r, int pos, int y, int z) {if (l r) {tr[x].cnt 1;tr[x].sum (qpow(2, y) * qpow(2, z)) % mod;return;}pushdown(x);int mid (l r) 1;if (pos mid)update_cnt(ls(x), l, mid, pos, y, z);elseupdate_cnt(rs(x), mid 1, r, pos, y, z);pushup(x);
}void update_sum(int x, int l, int r, int ql, int qr) {if (l ql r qr) {tr[x].lz;tr[x].sum (tr[x].sum * 2) % mod;return;}pushdown(x);int mid (l r) 1;if (ql mid)update_sum(ls(x), l, mid, ql, qr);if (qr mid)update_sum(rs(x), mid 1, r, ql, qr);pushup(x);
}LL query_cnt(int x, int l, int r, int ql, int qr) {if (l ql r qr) {return tr[x].cnt;}int mid (l r) 1;pushdown(x);LL ans 0;if (ql mid)ans query_cnt(ls(x), l, mid, ql, qr);if (qr mid)ans query_cnt(rs(x), mid 1, r, ql, qr);return ans;
}LL query_sum(int x, int l, int r, int ql, int qr) {if (l ql r qr) {return tr[x].sum;}int mid (l r) 1;LL ans 0;pushdown(x);if (ql mid)ans query_sum(ls(x), l, mid, ql, qr);if (qr mid)ans query_sum(rs(x), mid 1, r, ql, qr);return ans % mod;
}int main() {freopen(lcm.in, r, stdin);freopen(lcm.out, w, stdout);int n;while (~scanf(%d, n)) {for (int i 1; i n; i) {scanf(%d%d, a[i].x, a[i].y);}sort(a 1, a 1 n, cmp1);for (int i 1; i n; i) {a[i].rank i;}sort(a 1, a 1 n, cmp2);build(1, 1, n);LL ans 0;for (int i 1; i n; i) {LL tmp query_cnt(1, 1, n, 1, a[i].rank);update_cnt(1, 1, n, a[i].rank, tmp, a[i].x);ans (ans query_sum(1, 1, n, a[i].rank, n) * qpow(3, a[i].y) % mod) % mod;if (a[i].rank ! n)update_sum(1, 1, n, a[i].rank 1, n);}printf(%lld\n, ans);}
}
