由于间隔不变,对于下面 \(3\) 个操作,只需记录起始位置与间隔即可。
对于无数人到达酒店:所有位置的起始点 \(\times 2\),间隔 \(\times2\),新的团队起始点为 \(1\),间隔为 \(2\)。
对于 \(k\) 个人到达酒店:所有点的起始点 \(+k\) ,间隔不变,新的团队起始点为 \(0\),间隔为 \(1\)。
对于查询 \(g\) 团队的第 \(x\) 个人:找到起始点的坐标用间隔计算即可。
考虑如何实现查询位置 \(x\) 的所属团队。
从现在往前撤销加法或乘法操作。假设最后一个操作是乘法,那么如果位置 \(x\) 是奇数答案就是这个操作的团队编号。否则,撤销这个乘法操作,等价于将 \(x\) 除以 \(2\) 。现在最后是连续的一段加法操作,用前缀和 \(\mathcal O(1)\) 撤销这段操作即可。如果小于这个加法段,二分查找即可。发现每次撤销完连续加法操作,\(x\) 要么除以 \(2\) 要么退出循环,至多执行 \(30\) 次。
考场上本来过了这道题,但因为查询 \(g\) 团队的第 \(x\) 个人中的 \(g\) 可以为 \(0\),所以线段树要从 \(0\) 开始加而光荣爆 \(0\)。吐槽大样例没有这样的情况而数据全是这样的情况。
#define int ll
const int N = 3e5 + 5, p = 1e9 + 7;
struct segment_tree
{
int add[N << 2], mul[N << 2], sum[N << 2];
void pushup(int id) {
sum[id] = sum[id << 1] + sum[id << 1 | 1];
}
void pushdown(int id, int l, int r, int mid) {
if (mul[id] ^ 1) {
mul[id << 1] *= mul[id], mul[id << 1 | 1] *= mul[id];
mul[id << 1] %= p, mul[id << 1 | 1] %= p;
add[id << 1] *= mul[id], add[id << 1 | 1] *= mul[id];
add[id << 1] %= p, add[id << 1 | 1] %= p;
sum[id << 1] *= mul[id], sum[id << 1 | 1] *= mul[id];
sum[id << 1] %= p, sum[id << 1 | 1] %= p;
mul[id] = 1;
}
if (add[id]) {
sum[id << 1] += (mid - l + 1) * add[id], sum[id << 1 | 1] += (r - mid) * add[id];
sum[id << 1] %= p, sum[id << 1 | 1] %= p;
add[id << 1] += add[id], add[id << 1 | 1] += add[id];
add[id << 1] %= p, add[id << 1 | 1] %= p;
add[id] = 0;
}
}
void tadd(int l, int r, int x, int y, int k, int id) {
if (l > y || r < x) return ;
if (l >= x && r <= y) return sum[id] += (r - l + 1) * k, add[id] += k, sum[id] %= p, void();
int mid = l + r >> 1;
pushdown(id, l, r, mid);
tadd(l, mid, x, y, k, id << 1), tadd(mid + 1, r, x, y, k, id << 1 | 1);
pushup(id);
}
void tmul(int l, int r, int x, int y, int k, int id) {
if (l > y || r < x) return ;
if (l >= x && r <= y) return add[id] *= k, mul[id] *= k, sum[id] *= k, add[id] %= p, mul[id] %= p, sum[id] %= p, void();
int mid = l + r >> 1;
pushdown(id, l, r, mid);
tmul(l, mid, x, y, k, id << 1), tmul(mid + 1, r, x, y, k, id << 1 | 1);
pushup(id);
}
int query(int l, int r, int x, int y, int id) {
if (l > y || r < x) return 0;
if (l >= x && r <= y) return sum[id];
int mid = l + r >> 1;
pushdown(id, l, r, mid);
return (query(l, mid, x, y, id << 1) + query(mid + 1, r, x, y, id << 1 | 1)) % p;
}
} T1, T2;
int Q, pos[N], tot, cnt, n, s[N];
signed main()
{
// freopen("ex_hotel2.in", "r", stdin);
// freopen("my2.out", "w", stdout);
read(Q);
n = Q;
// T1 : 起始点
// T2 : 间隔
T2.tadd(0, n, 0, 0, 1, 1);
while (Q--)
{
int op, x, y;
read(op, x);
if (op == 1)
{
++tot;
s[tot] = s[tot - 1] + x;
if (x == 0)
{
pos[++cnt] = tot;
T1.tmul(0, n, 0, tot - 1, 2, 1);
T2.tmul(0, n, 0, tot - 1, 2, 1);
T1.tadd(0, n, tot, tot, 1, 1);
T2.tadd(0, n, tot, tot, 2, 1);
}
else
{
T1.tadd(0, n, 0, tot - 1, x, 1);
T2.tadd(0, n, tot, tot, 1, 1);
}
}
else if (op == 2)
{
read(y);
int st = T1.query(0, n, x, x, 1); // 起始点
int dis = T2.query(0, n, x, x, 1); // 间距
write((st + (y - 1) * dis % p) % p), ptc('\n');
}
else
{
int now = tot;
int k = x;
bool flg = 0;
for (int i = cnt; i >= 0; now = pos[i], --i)
{
int tmp = s[now] - s[pos[i]];
// cout << tmp << endl;
if (k >= tmp)
{
k -= tmp;
if (k % 2 == 1)
{
write(pos[i]), ptc('\n');
flg = 1;
break;
}
else
{
k /= 2;
}
}
else
{
int l = pos[i], r = now;
// cout << l << ' ' << r << endl;
while (l < r)
{
int mid = l + r >> 1;
if (k < s[now] - s[mid]) l = mid + 1;
else r = mid;
}
write(l), ptc('\n');
flg = 1;
break;
}
}
if (!flg) puts("0");
}
}
return 0;
}
标签:酒店,return,int,题解,间隔,起始,mid,无限,id
From: https://www.cnblogs.com/cyyhcyyh/p/18018302