题解

一、核心思路

学员会在走廊两端反弹。如果直接模拟，每个人每个时间都移动一次，显然无法承受。

我们把走廊展开成一个环，这样学员就可以看成一直沿着环向前走。

设：

$$L=2(N-1)$$

例如 N=6：

相位：  0 1 2 3 4 5 6 7 8 9
位置：  0 1 2 3 4 5 4 3 2 1

相位每增加 1，就对应学员前进一个时间单位。

---

二、base 是什么？

我们希望一个学员在时间 t 的相位可以统一写成：

$$\boxed{p=(base+t)\bmod L}$$

因此定义：

$$\boxed{base=出生时的初始相位-出生时间}$$

这样以后不需要模拟学员移动，只要知道 base 和当前时间 t，就能直接得到他的相位。

1. 向东 E

学员在时间 t、位置 y 向东。

他的初始相位就是：

$$y$$

所以：

$$\boxed{base=y-t}$$

2. 向西 W

位置 y 向西运动时，在展开后的环上对应的初始相位是：

$$L-y$$

所以：

$$\boxed{base=L-y-t}$$

所有 base 都对 L 取模。

---

三、相位如何转换成真实位置？

设当前相位为 p。

当：

$$0\le p<N$$

学员正在向东：

$$pos=p$$

当：

$$N\le p<L$$

学员正在向西：

$$pos=L-p$$

所以：

$$\boxed{ pos= \begin{cases} p,&p<N\\ L-p,&p\ge N \end{cases}}$$

---

四、查询区间如何转换？

查询：

$$Q\ t\ y\ z$$

要求真实位置：

$$[y,z)$$

第一段

在向东的部分：

$$pos=p$$

所以：

$$p\in[y,z)$$

第二段

在向西的部分：

$$pos=L-p$$

要求：

$$y\le L-p<z$$

得到：

$$p\in[L-z,L-y)$$

因此真实位置 [y,z) 对应两个相位区间：

$$\boxed{[y,z)}$$

和

$$\boxed{[L-z,L-y)}$$

---

五、从相位区间转换成 base 区间

我们知道：

$$p=(base+t)\bmod L$$

如果要求：

$$p\in[l,r)$$

那么：

$$base\in[l-t,r-t)\pmod L$$

因此查询时只需要在 base 上做环区间统计。

---

六、为什么用树状数组？

我们维护：

bit[x] 表示当前有多少名学员的 base=x。

放人

E t y z：

base = (y-t) mod L
add(base,z);

W t y z：

base = (L-y-t) mod L
add(base,z);

查询

真实区间 [y,z) 对应：

[y,z)
[L-z,L-y)

再减去当前时间 t，分别查询：

[y-t,z-t)
[L-z-t,L-y-t)

这些都是环上的区间。

环区间如果跨过 0，拆成：

[l,L) + [0,r)

即可。

---

七、特殊情况 N=1

只有 0 号教室，所有学员永远在 0。

所以直接维护总人数即可。

---

八、复杂度

每次修改和查询都只进行常数次树状数组操作：

$$\boxed{O(\log N)}$$

总复杂度：

$$\boxed{O(Q\log N)}$$

空间复杂度：

$$\boxed{O(N)}$$

---

九、完整代码

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=200005;

int n,q;
int bit[N*2];

int lowbit(int x){
    return x&-x;
}

void add(int x,int v){
    for(x++;x<=2*(n-1);x+=lowbit(x))
        bit[x]+=v;
}

int sum(int x){
    int res=0;
    for(x++;x>0;x-=lowbit(x))
        res+=bit[x];
    return res;
}

// 查询普通区间 [l,r)
int query(int l,int r){
    if(l>=r) return 0;
    return sum(r-1)-sum(l-1);
}

// 取模到 [0,L)
int mod(int x,int L){
    x%=L;
    if(x<0) x+=L;
    return x;
}

// 查询环上的 [l,r)
int circle(int l,int r,int L){
    l=mod(l,L);
    r=mod(r,L);

    if(l<r)
        return query(l,r);

    if(l>r)
        return query(l,L)+query(0,r);

    return 0;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>q;

    // N=1，所有人永远在 0 号教室
    if(n==1){
        int tot=0;

        while(q--){
            char op;
            int t,y,z;
            cin>>op>>t>>y>>z;

            if(op=='Q')
                cout<<tot<<"\n";
            else
                tot+=z;
        }

        return 0;
    }

    int L=2*(n-1);

    while(q--){
        char op;
        int t,y,z;
        cin>>op>>t>>y>>z;

        if(op=='E'){
            // 初始相位为 y
            // base = y-t
            int base=mod(y-t,L);
            add(base,z);
        }
        else if(op=='W'){
            // 初始相位为 L-y
            // base = L-y-t
            int base=mod(L-y-t,L);
            add(base,z);
        }
        else{
            int ans=0;

            // 真实位置 [y,z)
            // 对应相位 [y,z) 和 [L-z,L-y)

            // phase = base+t
            // 所以 base = phase-t
            ans+=circle(y-t,z-t,L);
            ans+=circle(L-z-t,L-y-t,L);

            cout<<ans<<"\n";
        }
    }

    return 0;
}