P3863

发表于 分类于
序列

序列

这个题比较神奇，我们采用扫描线的方法，并离线处理询问。

大概来说，就是这样的：

示意图

这里每条蓝色的线段表示在这个时间对序列进行了操作。

然后我们的每个询问实际上就是针对平面上的某个竖直向上的射线的信息的询问。

我不太好解释这个东西/kk。

假设现在我们扫描线扫到了一个位置 $x$，它对应序列轴上横坐标为 $x$ 的竖直线，表示现在我们要对 $p=x$ 的所有询问进行集中处理。

询问的就是该点在时间 $i-1$ 及之前（一直到 0）数值上大于等于 $y$ 的秒数，对应到这个平面上就是扫描线纵坐标小于等于 $i-1$ 的那一段中，统计一下这个大于等于 $y$ 的数的个数即可。

每次扫之前我们要先把红线和粉线进行操作，即在平行于扫描线的时间序列上加或减操作的数。

现在问题来了，我们一般的扫描线是线段树，似乎很难处理这类询问大于等于 $y$ 的数的个数之类的问题。。。

所以我们可以用分块维护。

这个分块维护的套路实际上比较入门。每个块内元素预先排序，查询的时候，对于整块二分得到个数，对于零散块直接暴力统计；对于修改操作，整块直接用 laztag，零散块暴力重构。

时间复杂度 $O(n\sqrt{n}\log n)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=1e5,M=1e3;

ll n,m,nn,cnt,cntq;
ll a[N+5],pos[N+5];

struct Opt{
  ll l,r,val,id;
  inline bool operator<(const Opt& rhs) const{return id<rhs.id;}
}opt[N+5];

struct Qry{ll id,pos,val,ans;}q[N+5];

inline bool Cmp1(Qry x,Qry y) {return x.pos<y.pos;}
inline bool Cmp2(Qry x,Qry y) {return x.id<y.id;}

struct node{
  ll val,id;
  inline node() {}
  inline node(ll x,ll y):val(x),id(y){}
  inline bool operator<(const node& rhs) const{return val<rhs.val;}
};

struct Block{node a[M+5];ll l,r,laz;}blo[M+5];

inline void Add(ll l,ll r,ll k) {
  if(pos[l]==pos[r]) {
    ll len=blo[pos[l]].r-blo[pos[l]].l+1;
    for(ll i=1;i<=len;i++) {
      ll tmp=blo[pos[l]].a[i].id;
      if(tmp>=l&&tmp<=r) blo[pos[l]].a[i].val+=k;
    }
    sort(blo[pos[l]].a+1,blo[pos[l]].a+len+1);
  }
  else {
    if(l==blo[pos[l]].l) {blo[pos[l]].laz+=k;}
    else {
      ll len=blo[pos[l]].r-blo[pos[l]].l+1;
      for(ll i=1;i<=len;i++) {
        ll tmp=blo[pos[l]].a[i].id;
        if(tmp>=l) blo[pos[l]].a[i].val+=k;
      }
      sort(blo[pos[l]].a+1,blo[pos[l]].a+len+1);
    }
    if(r==blo[pos[r]].r) {blo[pos[r]].laz+=k;}
    else {
      ll len=blo[pos[r]].r-blo[pos[r]].l+1;
      for(ll i=1;i<=len;i++) {
        ll tmp=blo[pos[r]].a[i].id;
        if(tmp<=r) blo[pos[r]].a[i].val+=k;
      }
      sort(blo[pos[r]].a+1,blo[pos[r]].a+len+1);
    }
    for(ll i=pos[l]+1;i<pos[r];i++) blo[i].laz+=k;
  }
}

inline ll Ask(ll l,ll r,ll k,ll x) {
  ll res=0;
  if(pos[l]==pos[r]) {
    ll len=blo[pos[l]].r-blo[pos[l]].l+1;
    for(ll i=1;i<=len;i++) {
      ll tmp=blo[pos[l]].a[i].id;
      if(tmp>=l&&tmp<=r) {
        res+=(blo[pos[l]].a[i].val+blo[pos[l]].laz+a[x]>=k);
      }
    }
  }
  else {
    ll len=blo[pos[l]].r-blo[pos[l]].l+1;
    for(ll i=1;i<=len;i++) {
      ll tmp=blo[pos[l]].a[i].id;
      if(tmp>=l) {
        res+=(blo[pos[l]].a[i].val+blo[pos[l]].laz+a[x]>=k);
      }
    }
    // printf("here:\n");
    // printf("l=%lld r=%lld\n",l,r);
    // printf("x=%lld res=%lld\n",x,res);
    len=blo[pos[r]].r-blo[pos[r]].l+1;
    for(ll i=1;i<=len;i++) {
      ll tmp=blo[pos[r]].a[i].id;
      if(tmp<=r) {
        res+=(blo[pos[r]].a[i].val+blo[pos[r]].laz+a[x]>=k);
      }
    }
    // printf("x=%lld res=%lld\n",x,res);
    for(ll i=pos[l]+1;i<pos[r];i++) {
      ll len=blo[i].r-blo[i].l+1;
      ll tmp=lower_bound(blo[i].a+1,blo[i].a+len+1
      ,node(k-blo[i].laz-a[x],0))-blo[i].a-1;
      res+=len-tmp;
    }
    // printf("x=%lld res=%lld\n",x,res);
  }
  return res;
}

int main() {

  n=read();m=read();
  nn=max(1ll,(ll)sqrt(m+1));
  for(ll i=1;i<=n;i++) {a[i]=read();}
  for(ll i=0,cntt=1;i<=m;i+=nn,cntt++) {
    blo[cntt].l=i;blo[cntt].r=i+nn-1;if(blo[cntt].r>m) blo[cntt].r=m;
    for(ll j=blo[cntt].l,k=1;j<=blo[cntt].r;j++,k++) {
      blo[cntt].a[k].val=0;blo[cntt].a[k].id=j;pos[j]=cntt;
    }
    ll len=blo[cntt].r-blo[cntt].l+1;
    sort(blo[cntt].a+1,blo[cntt].a+len+1);
  }

  for(ll i=1;i<=m;i++) {
    ll op=read();
    if(op==1) {
      ll l,r,x;l=read();r=read();x=read();
      opt[++cnt].l=i;opt[cnt].r=m;opt[cnt].val=x;opt[cnt].id=l;
      opt[++cnt].l=i;opt[cnt].r=m;opt[cnt].val=-x;opt[cnt].id=r+1;
    }
    if(op==2) {
      ll p,y;p=read();y=read();
      q[++cntq].id=i;q[cntq].pos=p;q[cntq].val=y;
    }
  }

  sort(opt+1,opt+cnt+1);sort(q+1,q+cntq+1,Cmp1);

  for(ll i=1,it=1,jt=1;i<=n;i++) {
    while(opt[it].id==i) {Add(opt[it].l,opt[it].r,opt[it].val);it++;}
    while(q[jt].pos==i) {q[jt].ans=Ask(0,q[jt].id-1,q[jt].val,i);jt++;}
  }

  sort(q+1,q+cntq+1,Cmp2);

  for(ll i=1;i<=cntq;i++) {writeln(q[i].ans);}

  return 0;
}