YbtOJ 755「分治」变量观测

#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;
}