题目描述

alt

解析

本题与D题的唯一区别就在于数据范围,对于D题，有一个很简单的思路为当第ii家公司的前两个要求为IQ,EQ时，需要最小的AQ能够满足条件。使用二维前缀和可以解决。 但是本题由于数据量过大，该方法肯定不可行。

先考虑二维时IQ与EQ，运用差分的思想，如图 alt

我们在每个顶点上标上1，每个交点标上-1，然后为了去掉重复的点，进行二位前缀和，我们可以得到下图 alt 然后思考三维，第三个维度可以理解为zz层二维平面，只有当前工作的zz小于该层的zz时，才可以在该层留下标记。然后进行三维前缀和即可。

代码

#include<bits/stdc++.h>
#include <random>
using namespace std;
 
template<class T>inline void read(T&x){
    char c,last=' ';
    while(!isdigit(c=getchar()))last=c;
    x=c^48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
    if(last=='-')x=-x;
}
 
#define P pair<int,int>
#define X first
#define Y second
const int MAXN=4e2+5,mod=998244353;
int n,q;
int a[MAXN][MAXN][MAXN];
vector<pair<int,P>>v;
set<P>st;
 
int qpow(int x,int p){
    int ret=1;
    for(;p;x=1ll*x*x%mod,p>>=1)if(p&1)ret=1ll*ret*x%mod;
    return ret;
}
 
P Pre(P p){
    set<P>::iterator it=st.lower_bound(p);
    --it;
    return *it;
}
 
P Next(P p){
    return *st.upper_bound(p);
}
 
int main()
{
    read(n),read(q);
    for(int i=1,m;i<=n;++i){
        read(m);
        vector<pair<int,P>>().swap(v);
        for(int k,x,y;m--;){
            read(k),read(x),read(y);
            v.push_back(make_pair(k,P(x,y)));
        }
        sort(v.begin(),v.end());
        st.clear();
        st.insert(P(0,401));
        st.insert(P(401,0));
        for(int i=0,k;i<v.size();++i){
            k=v[i].X;
            P p=v[i].Y;
            set<P>::iterator it=st.upper_bound(p);
            --it;
            if(it->Y<=p.Y)continue;
            ++a[k][Next(*it).X][it->Y];
            st.insert(p);
            --a[k][p.X][it->Y];
            while(Next(p).Y>=p.Y){
                P nxt=Next(p);
                --a[k][nxt.X][nxt.Y],++a[k][Next(nxt).X][nxt.Y];
                st.erase(nxt);
            }
            ++a[k][p.X][p.Y],--a[k][Next(p).X][p.Y];
        }
    }
    for(int k=1;k<=400;++k){
        for(int x=1;x<=400;++x){
            for(int y=1;y<=400;++y){
                a[k][x][y]+=a[k-1][x][y];
            }
        }
    }
    for(int k=1;k<=400;++k){
        for(int x=1;x<=400;++x){
            for(int y=1;y<=400;++y){
                a[k][x][y]+=a[k][x-1][y];
            }
        }
    }
    for(int k=1;k<=400;++k){
        for(int x=1;x<=400;++x){
            for(int y=1;y<=400;++y){
                a[k][x][y]+=a[k][x][y-1];
            }
        }
    }
    int seed;read(seed);
    std::mt19937 rng(seed);
    std::uniform_int_distribution<>u(1,400);
    int lastans=0,ans=0;
    for(int i=1;i<=q;i++){
        int IQ=(u(rng)^lastans)%400+1;
        int EQ=(u(rng)^lastans)%400+1;
        int AQ=(u(rng)^lastans)%400+1;
        lastans=a[IQ][EQ][AQ];
        ans=(ans+1ll*lastans*qpow(seed,q-i)%mod)%mod;
    }
    cout<<ans<<'\n';
    return 0;
}