C++(g++ 7.5.0) 解法, 执行用时: 2056ms, 内存消耗: 233040K, 提交时间: 2022-09-14 13:05:13

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int n,m;
struct node
{
    int l,r,sum;
}tr[N*40];
int root[N];
int tsz;

void create_nd (int &y) {
    tr[++tsz].sum = tr[y].sum;
    tr[tsz].l = tr[y].l;
    tr[tsz].r = tr[y].r;
    y = tsz;
}
 
void pushup(int u)
{
    tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}

void build(int &u,int l,int r)
{
    create_nd (u);
    if(l==r)
    {
        tr[u].sum=1;
        return ;
    }
    int mid=l+r>>1;
    build(tr[u].l,l,mid);
    build(tr[u].r,mid+1,r);
    pushup(u);
}

void update(int u,int &rt,int l,int r,int ql,int qr)
{
    if(!u)  return ;
    if(ql<=l&&r<=qr)
    {
        rt=u;
        return ;
    }
    create_nd(rt);
    int mid=l+r>>1;
    if(ql<=mid) update(tr[u].l,tr[rt].l,l,mid,ql,qr);
    if(qr>mid) update(tr[u].r,tr[rt].r,mid+1,r,ql,qr);
    pushup(rt);
}

int query(int u,int l,int r,int ql,int qr)
{
    if(!u) return 0;
    if(ql<=l&&r<=qr) return tr[u].sum;
    int mid=l+r>>1;
    int ans=0;
    if(ql<=mid) ans+=query(tr[u].l,l,mid,ql,qr);
    if(qr>mid) ans+=query(tr[u].r,mid+1,r,ql,qr);
    return ans;
}

int main()
{
    scanf("%d%d",&n,&m);
    build(root[0],1,n);
    for(int i=1;i<=m;i++)
    {
        int op;
        int x,y,L,R;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)
        {
            int val;
            scanf("%d",&val);
            update(root[val],root[val+1],1,n,x,y);
        }
        else{
            int l=0,r=i;
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(query(root[mid],1,n,x,y)) l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1639ms, 内存消耗: 327440K, 提交时间: 2022-10-20 16:51:35

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=6e5+10;
ll n,q,root[N],cnt;
bool lsy[N<<5];
ll ls[N<<5],rs[N<<5];
ll build(ll l,ll r)
{
	ll rt=++cnt;
	if(l==r)
	{
		lsy[rt]=1;
		return rt;
	}
	ll mid=(l+r)>>1;
	ls[rt]=build(l,mid);
	rs[rt]=build(mid+1,r);
	lsy[rt]=lsy[ls[rt]] | lsy[rs[rt]];
	return rt;
}
ll add(ll pre,ll now,ll l,ll r,ll x,ll y)
{
	if(x<=l&&y>=r)
	{
		return pre;
	}
	ll rt=++cnt;
	ls[rt]=ls[now],rs[rt]=rs[now],lsy[rt]=lsy[now];
	ll mid=(l+r)>>1;
	if(x<=mid) ls[rt]=add(ls[pre],ls[now],l,mid,x,y);
	if(y>mid) rs[rt]=add(rs[pre],rs[now],mid+1,r,x,y);
	lsy[rt]=lsy[ls[rt]] | lsy[rs[rt]];
	return rt;
}
bool query(ll i,ll l,ll r,ll x,ll y)
{
	if(i==0) return false;
	if(x<=l&&y>=r) return lsy[i];
	bool ans=false;
	ll mid=(l+r)>>1;
	if(x<=mid) ans|=query(ls[i],l,mid,x,y);
	if(y>mid) ans|=query(rs[i],mid+1,r,x,y);
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	root[0]=build(1,n);
	while(q--)
	{
		ll op,l,r,x;
		cin>>op>>l>>r;
		if(op==1)
		{
			cin>>x;
			if(root[x]==0) continue;
			root[x+1]=add(root[x],root[x+1],1,n,l,r);
		}
		else
		{
			ll lll=0,rrr=N;
			while(lll<rrr)
			{
				ll mid=(lll+rrr+1)>>1;
				if(query(root[mid],1,n,l,r)) lll=mid;
				else rrr=mid-1;
			}
			cout<<lll<<"\n";
		}
	}
}