YbtOJ 755「分治」变量观测

(Updated: )
oi
,

题目链接：YbtOJ #755

小 A 有 $n$ 个变量，分别为 $x_{1\sim n}$。

接下来依次发生了 $q$ 次事件，分为两种形式：

  • 1 t k q[1] q[2] ... q[k]：假设这是第 $p$ 次 $1$ 操作，则设置一个编号为 $p$ 的观测员，直到 $x_{q_1},x_{q_2},\cdots x_{q_k}$ 与当前相比变化总值大于等于 $t$ 时结束观测。（保证同一个观测员的 $q_{1\sim k}$ 各不相同）
  • 2 i v：给 $x_i$ 加上 $v$。你需要输出所有在这次操作结束观测的观测员编号。

强制在线。

$n,m \le 2\times10^5$，$1\le k\le3$，$1\le t,v\le10^6$。

Solution

考虑将每个人观测时间分为 $k$ 份，每份 $\lceil \frac tk \rceil$，丢到每个变量对应的 set 里。

显然变化量大于等于 $t$ 的必要条件是需要有一个变量的变化值超过 $\lceil \frac tk \rceil$。

这样每个变量增加的时候不断从 set 里取出，然后扫一遍其他变量的变化值，如果达到则从 set 中删去，如果没达到则在此基础上重新计算一遍重新分一遍。

由于 $k\leq 3$，那么某一份到达则剩余值不超过原先值得 $\frac 23$。

那么每个观察员最多进行 $\log_{1.5}V$ 次操作。

时间复杂度看着就能过反正。

反正人傻常数大，跑的最慢。

Code

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
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2e5+10;
int n,q,cp,b[N],g[N][4];
struct node{vector<int> q;int t;}a[N];
vector<int> A;
#define pb push_back
struct PA{int v,p;};
I bool operator < (Cn PA& A,Cn PA& B){return A.v^B.v?A.v<B.v:A.p<B.p;}
#define MP(x,y) ((PA){x,y})
multiset<PA> s[N];
#define div(x,y) ((x)/(y)+((x)%(y)>0))
I void Add(CI id,CI t,CI k,CI p){
    RI i,x;for(a[id].q.clear(),i=1;i<=k;i++) read(x),x^=p,a[id].q.pb(x);a[id].t=t;
    for(i=1;i<=k;i++) s[a[id].q[i-1]].insert(MP(div(t,k)+(g[id][i]=b[a[id].q[i-1]]),id));
}
I int Sol(CI i,CI v){
    A.clear(),b[i]+=v;W(!s[i].empty()&&(*s[i].begin()).v<=b[i]){
        PA u=*s[i].begin();RI S=0;
        for(RI sz=a[u.p].q.size(),j=0;j<sz;j++) S+=b[a[u.p].q[j]]-g[u.p][j+1],assert(b[a[u.p].q[j]]>=g[u.p][j+1]),s[a[u.p].q[j]].erase(s[a[u.p].q[j]].find(MP(div(a[u.p].t,sz)+g[u.p][j+1],u.p)));
        if(S>=a[u.p].t){A.pb(u.p);continue ;}a[u.p].t-=S;
        for(RI sz=a[u.p].q.size(),j=0;j<sz;j++) s[a[u.p].q[j]].insert(MP(div(a[u.p].t,sz)+(g[u.p][j+1]=b[a[u.p].q[j]]),u.p));
    }write(A.size()),pc(' '),sort(A.begin(),A.end());for(auto i:A) write(i),pc(' ');pc('\n');return A.size();
}
int main(){
    freopen("obs.in","r",stdin),freopen("obs.out","w",stdout);
    RI i,op,x,y,p=0;for(read(n,q),i=1;i<=q;i++) read(op,x,y),x^=p,op&1?Add(++cp,x,y,p):(y^=p,p=Sol(x,y),void());return 0;
}