一直Judging求调
查看原帖
一直Judging求调
120438
Lacrymabre楼主2021/10/7 14:22

rt,不知道为什么会这样,是不是代码哪里出了问题?

算法事ODT

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#define ll long long
#define _it set<node>::iterator
using namespace std;

inline long long read(){
    ll f=1,s=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*f;
}

struct node{
	ll l,r;
	mutable ll v;
	node(ll L,ll R=-1,ll V=0){l=L;r=R;v=V;}
    bool operator<(const node &x)const{
        return l<x.l;
    }
};
set<node>odt;
ll n,m,s[100001],x,y;

_it spilt(ll ops){
	_it it=odt.lower_bound(node(ops,ops,0));
    if(it!=odt.end()&&it->l==ops) return it;
    it--;
    ll L=it->l,R=it->r,V=it->v;
    odt.erase(it);
    odt.insert(node(L,ops-1,V));
    return odt.insert(node(ops,R,V)).first;
}

void push_tar(ll l,ll r,ll z){
	_it R=spilt(r+1),L=spilt(l);
	odt.erase(L,R);
	odt.insert(node(l,r,z));
}

ll query(ll l,ll r){
	ll res=0;
	map<int,int>q;q.clear();
	_it R=spilt(r+1),L=spilt(l);
	while(L!=R){
		if(!q[L->v]) res++,q[L->v]=1;
		L++; 
	}
	return res;
}

int main(){
	n=read();
	odt.insert(node(1,n,0));
	for(int i=1;i<=n;i++){
		s[i]=read();
		push_tar(i,i,s[i]);
	}
	m=read();
	while(m-->0){
		x=read();y=read();
		cout<<query(x,y)<<"\n";
	}
	return 0;
}
2021/10/7 14:22
加载中...