Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

为啥MLE啊，各位acmer大佬来康康，救救孩子，卡一晚上了

Posted by nbucty at 2020-02-12 21:16:32 on Problem 2528
```#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=10223;
struct node{
int l,r;
int val;
int lazy;
}tr[N*8];
struct q{
int l,r;
}q[N];
int ans[N];
void pushup(int u){
if(!tr[u<<1].val||!tr[u<<1|1].val||tr[u<<1].val!=tr[u<<1|1].val)
tr[u].val=0;
else
tr[u].val=tr[u<<1].val;
}
void pushdown(int u){
if(tr[u].lazy){
tr[u<<1].val=tr[u<<1|1].val=tr[u].val;
tr[u<<1].lazy=tr[u<<1|1].lazy=tr[u].lazy;
tr[u].lazy=0;
}
}
void build(int u,int l,int r){
if(l==r){
tr[u].l=tr[u].r=l;
tr[u].val=-1;
tr[u].lazy=0;
}
else{
tr[u].l=l;
tr[u].r=r;
tr[u].val=-1;
tr[u].lazy=0;
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
}
}
void modify(int u,int l,int r,int x){
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].val=x;
tr[u].lazy=x;
}
else{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)
modify(u<<1,l,r,x);
if(r>mid)
modify(u<<1|1,l,r,x);
pushup(u);
}
}
vector<int> num;
int find(int x){
return lower_bound(num.begin(),num.end(),x)-num.begin()+1;
}
void query(int u,int l,int r){
if(tr[u].val==-1)
return ;
else if(tr[u].val){
ans[tr[u].val]++;
return ;
}
else{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
query(u<<1,l,r);
query(u<<1|1,l,r);
return ;
}
}
int main(){
int t;
cin>>t;
while(t--){
int n;
memset(ans,0,sizeof ans);
cin>>n;
int i;
num.clear();
for(i=1;i<=n;i++){
scanf("%d%d",&q[i].l,&q[i].r);
num.push_back(q[i].l);
num.push_back(q[i].r);
}
sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());
for(i=0;i<(int)num.size()-1;i++){
if(num[i+1]-num[i]>1)
num.push_back(num[i+1]-1);
}
sort(num.begin(),num.end());
int size=num.size();
build(1,1,size);
for(i=1;i<=n;i++){
int l=find(q[i].l);
int r=find(q[i].r);
modify(1,l,r,i);
}
query(1,1,size);
int res=0;
for(i=1;i<=n;i++)
if(ans[i])
res++;
cout<<res<<endl;
}
}

```

Followed by: