今晚ABC F
2026-09-26 21:52:50
发布于：广东
39阅读
0回复
0点赞
按行做前缀主席树。
区间加要带 lazytag，那咋办。那标记永久化呗。
做完了。
namespace cjdst{
const int N = 200000, M = 12000000;
int left[N + 5], right[N + 5];
int lson[M + 5], rson[M + 5];
ll tr[M + 5], lazytag[M + 5];
int pre[N + 5];
int ctnode;
int n, m, q;
void build(int &u, int l, int r){
if(!u) u = (++ctnode);
if(l == r) return;
int mid = (l + r) >> 1;
build(lson[u], l, mid);
build(rson[u], mid + 1, r);
}
void modify(int &u, int lst, int l, int r, int l2, int r2){
u = (++ctnode);
lazytag[u] = lazytag[lst];
if(l >= l2 && r <= r2){
tr[u] = tr[lst] + (r - l + 1);
lazytag[u]++;
lson[u] = lson[lst];
rson[u] = rson[lst];
return;
}
int mid = (l + r) >> 1;
if(l2 > mid){
lson[u] = lson[lst];
}else{
modify(lson[u], lson[lst], l, mid, l2, r2);
}
if(r2 <= mid){
rson[u] = rson[lst];
}else{
modify(rson[u], rson[lst], mid + 1, r, l2, r2);
}
tr[u] = tr[lson[u]] + tr[rson[u]] + lazytag[u] * (r - l + 1);
}
ll query(int u, int l, int r, int l2, int r2){
if(l >= l2 && r <= r2) return tr[u];
int mid = (l + r) >> 1;
ll ans = (std::min(r, r2) - std::max(l, l2) + 1) * lazytag[u];
if(l2 <= mid) ans += query(lson[u], l, mid, l2, r2);
if(r2 > mid) ans += query(rson[u], mid + 1, r, l2, r2);
return ans;
}
void solve(){
std::cin >> n >> m >> q;
build(pre[0], 1, m);
for(int i = 1; i <= n; i++){
std::cin >> left[i] >> right[i];
modify(pre[i], pre[i - 1], 1, m, left[i], right[i]);
}
while(q--){
int u, d, l, r;
std::cin >> u >> d >> l >> r;
std::cout << query(pre[d], 1, m, l, r) - query(pre[u - 1], 1, m, l, r) << '\n';
}
}
}
时间复杂度：。
有帮助，赞一个