跳蚤
题目描述
NiroBC 姐姐奴役了一群跳蚤，并随时把它们丢到一台图灵机的纸带上。
一开始，纸带上没有跳蚤，每一个时刻，NiroBC 姐姐可能做以下三个操作之一：
- 在位置x 放置一只每次向右（坐标增大方向）跳t 格的跳蚤。
- 命令所有跳蚤向右跳跃一次，跳跃的距离为各自的t。
- 给定区间[l,r]，求该区间内跳蚤的个数。
输入
第一行一个正整数Q，表示操作个数。
接下来Q 行，这Q 行中的第i 行含有若干个整数，描述第i 个操作。
(1) 若第一个整数为1，则紧跟两个整数xi 和ti，表示在xi 的位置放置一只每次向右跳跃ti 格的跳蚤。
(2) 若第一个整数为2，则命令所有跳蚤向右跳跃一次。
(3) 若第一个整数为3，则紧跟两个整数li 和ri，你需要输出此时区间[li, ri]中跳蚤的数量。
输出
对于每一个3 号操作，输出一行一个整数，表示该询问的答案。
样例输入
10
1 4 1
1 2 2
3 3 5
2 3
3 5
2 3
3 5
3 6 6
1 5 1
3 3 5
样例输出
1
2
0
2
1
思路：
取(B=200)，对于(tleq B)的跳蚤，直接建(B)颗线段树，将(t)相同的跳蚤放在一起。
对于(t>B)的跳蚤，最多跳(1e5/200)次就不会在被记录到，我们暴力模拟，并用树状数组记录下它们的位置。
另外，设(C)为到(i)为止的跳跃次数，对于所有(t)相同的跳蚤来说，每次跳跃并不改变其相对位置，且其相对位置只与插入时间有关。
所以我们每次只需把跳蚤插入到(x-C*t)的位置即可。
code：
\#pragma GCC optimize(2)
\#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N=1e6+5;
const ll mod=100000007;
const double eps=1e-5;
const double pi=acos(-1);
#define ls p<<1
#define rs p<<1|1
int c[N],tl,rt[N],n;
int C;
struct node
{
int l,r;
int dat;
}a[N];
pii q[N];
void add(int x,int d)
{
for(int i=x;i<=100000;i+=i&-i)
c[i]+=d;
}
int ask(int x)
{
int ans=0;
for(int i=x;i;i-=i&-i) ans+=c[i];
return ans;
}
void build(int &p,int l,int r,int x)
{
if(!p) p=++n;
if(l==r)
{
a[p].dat++;
return;
}
int mid=l+r>>1;
if(x<=mid) build(a[p].l,l,mid,x);
else build(a[p].r,mid+1,r,x);
a[p].dat=a[a[p].l].dat+a[a[p].r].dat;
}
int query(int p,int l,int r,int x,int y)
{
if(!p) return 0;
if(l>=x&&r<=y) return a[p].dat;
int mid=l+r>>1;
int ans=0;
if(x<=mid) ans+=query(a[p].l,l,mid,x,y);
if(y>mid) ans+=query(a[p].r,mid+1,r,x,y);
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int _;
cin>>_;
while(_--)
{
int op;
cin>>op;
if(op==1)
{
int x,t;
cin>>x>>t;
if(t>200)
{
add(x,1);
q[++tl]={x,t};
}
else build(rt[t],-t*100000,100000,x-C*t);
}
if(op==2)
{
C++;
int cnt=0;
for(int i=1;i<=tl;i++)
{
add(q[i].first,-1);
if(q[i].first+q[i].second<=100000)
q[++cnt]={q[i].first+q[i].second,q[i].second};
}
tl=cnt;
for(int i=1;i<=cnt;i++) add(q[i].first,1);
}
if(op==3)
{
int l,r;
cin>>l>>r;
int ans=ask(r)-ask(l-1);
for(int i=1;i<=200;i++)
ans+=query(rt[i],-i*100000,100000,l-C*i,r-C*i);
printf("%d
",ans);
}
}
return 0;
}