NC17879. 线段树
描述
输入描述
第一行两个整数n,m
接下来m行，每行包含四个整数op,l,r,a，表示一次操作，其中op表示操作类型
1≤n,m≤100000
1≤l≤r≤n
1≤op≤2
-100000≤a≤100000
输出描述
对每个操作2，输出一行，包含一个整数表示答案
示例1
输入:
3 3 1 2 3 9 2 1 2 1 2 1 3 1
输出:
1 1
C++14(g++5.4) 解法, 执行用时: 3325ms, 内存消耗: 5412K, 提交时间: 2019-02-28 16:47:40
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define dep(i, a, b) for (int i = (a); i >= (b); --i)
#define mp make_pair
#define ft first
#define sc second
#define pb push_back
#define pii pair<int, int>
using namespace std;
int qreadInt() {
int x = 0; char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) (x *= 10) += (ch - '0'), ch = getchar();
return x;
}
typedef long long i64;
const int N = 100010;
int _(int l, int r) {
int x;
assert(scanf("%d", &x) == 1 && l <= x && x <= r);
return x;
}
int n, m, ans;
struct range {
int l, d;
bool operator<(const range& w) const { return d != w.d ? d < w.d : l < w.l; }
} rs[N * 2];
struct point {
i64 y;
int l, r;
bool operator<(const point& p) const { return y < p.y; }
} ps0[N * 2], *_ps = ps0, tmp1[10000], tmp2[10000], tmp0[4];
struct block {
point* ps;
i64 a;
int l, r, pp, d;
void init(range* a, int n) {
pp = n;
ps = _ps, _ps += pp;
for (int i = 0; i < n; ++i) ps[i] = (point){ 0, a[i].l, a[i].l + a[i].d };
this->a = 0;
d = a[0].d + 1;
l = ps[0].l;
r = ps[pp - 1].r;
}
void modify(int L, int R, i64 a) {
i64 ad = a * d;
if (L <= l && r <= R)
this->a += ad;
else if (L <= r && l <= R) {
int p1 = 0, p2 = 0, p0 = 0;
for (int i = 0; i < pp; ++i) {
if (L <= ps[i].l && ps[i].r <= R) {
ps[i].y += ad;
tmp1[p1++] = ps[i];
} else if (L > ps[i].r || R < ps[i].l)
tmp2[p2++] = ps[i];
else {
ps[i].y += a * (std::min(R, ps[i].r) - std::max(L, ps[i].l) + 1);
tmp0[p0++] = ps[i];
}
}
if (p0) {
std::sort(tmp0, tmp0 + p0);
std::merge(tmp0, tmp0 + p0, tmp2, tmp2 + p2, tmp2 + p2);
std::merge(tmp1, tmp1 + p1, tmp2 + p2, tmp2 + p2 + p2 + p0, ps);
} else
std::merge(tmp1, tmp1 + p1, tmp2, tmp2 + p2, ps);
}
}
void query(int L, int R, i64 a) {
if (L <= l && r <= R)
ans += std::upper_bound(ps, ps + pp, point{ a - this->a, 0 }) - ps;
else if (L <= r && l <= R) {
a -= this->a;
for (int i = 0; i < pp; ++i)
if (L <= ps[i].l && ps[i].r <= R && ps[i].y <= a)
++ans;
}
}
};
struct seq {
block* bs;
int bp;
void init(range* a, int n) {
int bsz = sqrt(n * log2(n)) / 4 + 1;
bp = (n - 1) / bsz + 1;
bs = new block[bp];
for (int i = 0, l = 0, r; i < bp; ++i, l = r) {
r = std::min(n, l + bsz);
bs[i].init(a + l, r - l);
}
}
void modify(int l, int r, i64 a) {
for (int i = 0; i < bp; ++i) bs[i].modify(l, r, a);
}
void query(int l, int r, i64 a) {
for (int i = 0; i < bp; ++i) bs[i].query(l, r, a);
}
} ss[50];
int rp = 0, sp = 0;
int main() {
n = _(1, 100000), m = _(1, 100000);
rs[rp++] = (range){ 1, n - 1 };
for (int i = 0; i < rp; ++i) {
int l = rs[i].l, r = l + rs[i].d, m = (l + r) / 2, m1 = m + 1;
if (l < r) {
rs[rp++] = (range){ l, m - l };
rs[rp++] = (range){ m1, r - m1 };
}
}
std::sort(rs, rs + rp);
for (int i = 0, j = 0; i < rp; i = j) {
int d = rs[i].d;
for (++j; j < rp && rs[j].d == d; ++j)
;
ss[sp++].init(rs + i, j - i);
}
while (m--) {
int op = _(1, 2), l = _(1, n), r = _(l, n), a = _(-1000000000, 1000000000);
switch (op) {
case 1:
for (int i = 0; i < sp; ++i) ss[i].modify(l, r, a);
break;
case 2:
ans = 0;
for (int i = 0; i < sp; ++i) ss[i].query(l, r, a);
printf("%d\n", ans);
break;
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 3973ms, 内存消耗: 5432K, 提交时间: 2018-08-17 22:47:55
#include<bits/stdc++.h>
typedef long long i64;
const int N=100010;
int _(int l,int r){
int x;
assert(scanf("%d",&x)==1&&l<=x&&x<=r);
return x;
}
int n,m,ans;
struct range{
int l,d;
bool operator<(const range&w)const{
return d!=w.d?d<w.d:l<w.l;
}
}rs[N*2];
struct point{
i64 y;
int l,r;
bool operator<(const point&p)const{return y<p.y;}
}ps0[N*2],*_ps=ps0,tmp1[10000],tmp2[10000],tmp0[4];
struct block{
point*ps;
i64 a;
int l,r,pp,d;
void init(range*a,int n){
pp=n;
ps=_ps,_ps+=pp;
for(int i=0;i<n;++i)ps[i]=(point){0,a[i].l,a[i].l+a[i].d};
this->a=0;
d=a[0].d+1;
l=ps[0].l;
r=ps[pp-1].r;
}
void modify(int L,int R,i64 a){
i64 ad=a*d;
if(L<=l&&r<=R)this->a+=ad;
else if(L<=r&&l<=R){
int p1=0,p2=0,p0=0;
for(int i=0;i<pp;++i){
if(L<=ps[i].l&&ps[i].r<=R){
ps[i].y+=ad;
tmp1[p1++]=ps[i];
}else if(L>ps[i].r||R<ps[i].l)tmp2[p2++]=ps[i];
else{
ps[i].y+=a*(std::min(R,ps[i].r)-std::max(L,ps[i].l)+1);
tmp0[p0++]=ps[i];
}
}
if(p0){
std::sort(tmp0,tmp0+p0);
std::merge(tmp0,tmp0+p0,tmp2,tmp2+p2,tmp2+p2);
std::merge(tmp1,tmp1+p1,tmp2+p2,tmp2+p2+p2+p0,ps);
}else std::merge(tmp1,tmp1+p1,tmp2,tmp2+p2,ps);
}
}
void query(int L,int R,i64 a){
if(L<=l&&r<=R)ans+=std::upper_bound(ps,ps+pp,point{a-this->a,0})-ps;
else if(L<=r&&l<=R){
a-=this->a;
for(int i=0;i<pp;++i)if(L<=ps[i].l&&ps[i].r<=R&&ps[i].y<=a)++ans;
}
}
};
struct seq{
block*bs;
int bp;
void init(range*a,int n){
int bsz=sqrt(n*log2(n))/4+1;
bp=(n-1)/bsz+1;
bs=new block[bp];
for(int i=0,l=0,r;i<bp;++i,l=r){
r=std::min(n,l+bsz);
bs[i].init(a+l,r-l);
}
}
void modify(int l,int r,i64 a){
for(int i=0;i<bp;++i)bs[i].modify(l,r,a);
}
void query(int l,int r,i64 a){
for(int i=0;i<bp;++i)bs[i].query(l,r,a);
}
}ss[50];
int rp=0,sp=0;
int main(){
n=_(1,100000),m=_(1,100000);
rs[rp++]=(range){1,n-1};
for(int i=0;i<rp;++i){
int l=rs[i].l,r=l+rs[i].d,m=(l+r)/2,m1=m+1;
//printf("[%d,%d]",l,r);
if(l<r){
rs[rp++]=(range){l,m-l};
rs[rp++]=(range){m1,r-m1};
}
}
std::sort(rs,rs+rp);
for(int i=0,j=0;i<rp;i=j){
int d=rs[i].d;
for(++j;j<rp&&rs[j].d==d;++j);
ss[sp++].init(rs+i,j-i);
}
while(m--){
int op=_(1,2),l=_(1,n),r=_(l,n),a=_(-1000000000,1000000000);
switch(op){
case 1:
for(int i=0;i<sp;++i)ss[i].modify(l,r,a);
break;
case 2:
ans=0;
for(int i=0;i<sp;++i)ss[i].query(l,r,a);
printf("%d\n",ans);
break;
default:
assert(0);
}
}
return 0;
}