LOJ503 ZQC的课堂

题意

叮铃铃 …… 上课铃响了。
「啊,又是无聊的math」,坐在教室里的ZQC这样想道。Mr.Sam今天在课上讲了平面直角坐标系上的向量。「这不是幼儿园姿势么」,ZQC实在忍不住,睡着了。Mr.Sam把ZQC给叫醒,并给了他这样一道题:
假设有一平面直角坐标系,ZQC有一支画笔,起点是$(1,1)$,现在有$n$个向量,第$i$个向量形如$(x_i,y_i)$,且满足每一个向量都满足$x_i,y_i$均为偶数。ZQC按顺序根据这些向量改变自己的画笔的位置,即位置依次改变成$(1+x_1,1+y_1),(1+x_1+x_2,1+y_1+y_2) \ldots$。每次改变位置时,画笔都沿两点之间的最短距离移动。结束时,画笔的运动轨迹一定由$n$条线段组成。Mr.Sam要ZQC回答这些线段穿过$x$轴和$y$轴的总次数之和是多少。
但这样的问题对ZQC来说太简单了,于是Mr.Sam设定了一个指针,一开始指在第一个向量。现在他做了$q$个操作,操作有四种,分别是:
B表示把指针向后移动,如果越界则视为无效。即,如果设指针移动前的位置是$i$,那么移动后的位置是$\max(1,i-1)$。
F表示把指针向前移动,如果越界则视为无效。即,如果设指针移动前的位置是$i$,那么移动后的位置是$\min(n,i+1)$。
C nx ny把当前指针所指的向量修改为$(nx,ny)$,这里同样满足$nx,ny$为偶数。
Q假设ZQC从起点开始,按第$1$个到第$n$个的顺序沿向量走,询问画出的$n$条线段穿过$x$轴和$y$轴次数的总和。
$n \leqslant 10^5,q \leqslant 3 \times 10^5$

题解

这道题首先会注意到一个性质,就是一次操作只会移动一个单位,因此可以考虑在移动操作的时候,维护一些东西:
对于指针左侧的答案,我们直接暴力维护答案即可。比如说,对于左移操作,假如操作前位于位置$i$,我们直接删去第$i$个向量对答案的贡献,右移操作类似。对于右侧的答案,考虑用线段树维护答案。用线段树维护答案的时候,采用动态开点。对于一个向量,我们只需要在这个向量对应的区间加值。这个对应的区间,我们可以通过先确定最后一个点对应的区间,再通过最后一个点倒退过来得到每个区间的位置。查询时,对一个对应的位置查询值即可。但是修改操作要怎么处理呢?修改时,首先把指针左侧暴力维护的答案更新一下,再将右侧线段树查询的位置更新一下即可。
实现上可以参考一下代码,有点讲不清= =。

代码

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=1e5+10;
const int maxnode=1e7+10;
const int Max=1e8;
int posx[maxn],posy[maxn],prex[maxn],prey[maxn],sufx[maxn],sufy[maxn],ansx[maxn],ansy[maxn];
int rtx,rty;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
struct Segment_Tree{
struct node{
int l,r;
}Tree[maxnode];
int Tag[maxnode];
int cnt;
inline void Modify(int &pos,int l,int r,int L,int R,int val){
if(!pos)pos=++cnt;
if(L<=l && r<=R){
Tag[pos]+=val;
return;
}
int mid=(l+r)>>1;
if(L<=mid)Modify(Tree[pos].l,l,mid,L,R,val);
if(R>mid)Modify(Tree[pos].r,mid+1,r,L,R,val);
}
inline int Query(int pos,int l,int r,int Pos){
if(!pos)return 0;
if(l==r)return Tag[pos];
int mid=(l+r)>>1;
if(Pos<=mid)return Tag[pos]+Query(Tree[pos].l,l,mid,Pos);
else return Tag[pos]+Query(Tree[pos].r,mid+1,r,Pos);
}
}T;
inline void GetPre(int pos){
prex[pos]=prex[pos-1]+posx[pos];prey[pos]=prey[pos-1]+posy[pos];
ansx[pos]=ansx[pos-1]+((prex[pos]>0)^(prex[pos-1]>0));
ansy[pos]=ansy[pos-1]+((prey[pos]>0)^(prey[pos-1]>0));
}
inline void GetSuf(int pos){
sufx[pos]=sufx[pos+1]-posx[pos];sufy[pos]=sufy[pos+1]-posy[pos];
}
inline void Update(int pos,int val){
int l=sufx[pos],r=sufx[pos+1];
if(l>r)swap(l,r);
T.Modify(rtx,-Max,Max,l,r,val);
l=sufy[pos],r=sufy[pos+1];
if(l>r)swap(l,r);
T.Modify(rty,-Max,Max,l,r,val);
}
int main(){
int i,j,k,m,n,q;
#ifndef ONLINE_JUDGE
freopen("LOJ503.in","r",stdin);
freopen("LOJ503.out","w",stdout);
#endif
n=read();
for(i=1;i<=n;i++){
posx[i]=read();posy[i]=read();
}
prex[0]=prey[0]=1;
for(i=1;i<=n;i++)GetPre(i);
for(i=n;i>=1;i--)GetSuf(i);
for(i=n;i>=2;i--)Update(i,1);
int pos=1;
q=read();
while(q--){
char ch=getchar();
while(!isalpha(ch))ch=getchar();
if(ch=='B'){
if(pos==1)continue;
GetSuf(pos);
Update(pos,1);
pos--;
}
if(ch=='F'){
if(pos==n)continue;
pos++;
GetPre(pos);
Update(pos,-1);
}
if(ch=='C'){
int x=read(),y=read();
posx[pos]=x,posy[pos]=y;
GetPre(pos);
}
if(ch=='Q'){
int x=sufx[pos+1]-prex[pos],y=sufy[pos+1]-prey[pos];
printf("%d\n",ansx[pos]+ansy[pos]+T.Query(rtx,-Max,Max,x)+T.Query(rty,-Max,Max,y));
}
}
return 0;
}