TLE自动机 @ 2019-10-04 15:51:59
我交了一页。。。
看有很多人80的都是too short on 525 啊,有没有做过的大佬看看
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define inf 1926081700
#define alpha 0.75
#define ll long long
using namespace std;
int read(){
int x=0,pos=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return pos?x:-x;
}
const int N = 400001;
int n,k,ans,lnk[N],lst[N],rub[N];
struct sqr{
int x1,x2,y1,y2;
}q;
struct point{
int x[2],cnt;
}p[N],pn;
struct node{
int mi[2],mx[2],sz,sum;point c;
}t[N];
int rt,D,rs[N],ls[N],top,tot;
int operator < (point a,point b){
return a.x[D]<b.x[D];
}
void push_up(int now){
int l=ls[now],r=rs[now];t[now].sz=t[l].sz+t[r].sz+1;t[now].sum=t[l].sum+t[r].sum+t[now].c.cnt;
for(register int i=0;i<=1;i++){
t[now].mi[i]=t[now].mx[i]=t[now].c.x[i];
if(l) t[now].mi[i]=min(t[now].mi[i],t[l].mi[i]),t[now].mx[i]=max(t[now].mx[i],t[l].mx[i]);
if(r) t[now].mi[i]=min(t[now].mi[i],t[r].mi[i]),t[now].mx[i]=max(t[now].mx[i],t[r].mx[i]);
}
}
inline int newnode(){
if(top) return rub[top--];
else return ++tot;
}
inline int build(int l,int r,int d){
if(l>r) return 0;
int now=newnode(),mid=(l+r)>>1;
D=d,nth_element(p+l,p+mid,p+r+1);
t[now].c=p[mid],ls[now]=build(l,mid-1,d^1),rs[now]=build(mid+1,r,d^1);
push_up(now); return now;
}
inline void clear(int now,int pos){
if(ls[now]) clear(ls[now],pos);
p[pos+t[ls[now]].sz+1]=t[now].c,rub[++top]=now;
if(rs[now]) clear(rs[now],pos+t[ls[now]].sz+1);
}
inline void check(int &now,int d){
if(alpha*(double)(t[now].sz)<(double)(t[ls[now]].sz)||alpha*(double)(t[now].sz)<(double)(t[rs[now]].sz)){
clear(now,0);now=build(1,t[now].sz,d);
}
}
inline void insert(int &now,point p,int d){
if(!now){
now=newnode();ls[now]=rs[now]=0;t[now].c=p;push_up(now);return;
}
if(p.x[d]<=t[now].c.x[d]){
insert(ls[now],p,d^1);
}else{
insert(rs[now],p,d^1);
}
push_up(now);check(now,d);
}
int chkin(int now,sqr tp){
return (!(t[now].mx[0]<tp.x1||t[now].mi[0]>tp.x2||t[now].mx[1]<tp.y1||t[now].mi[1]>tp.y2));
}
int totalin(int now,sqr tp){
return (t[now].mx[0]<=tp.x2&&t[now].mi[0]>=tp.x1&&t[now].mx[1]<=tp.y2&&t[now].mi[1]>=tp.y1);
}
int ptin(point a,sqr b){
return (b.x2>=a.x[0]&&b.x1<=a.x[0]&&b.y1<=a.x[1]&&b.y2>=a.x[1]);
}
inline int query(int now,sqr tp){
if(!now) return 0;
int re=0;
if(totalin(now,tp)){
return t[now].sum;
}else if(!chkin(now,tp)) return 0;
if(ptin(t[now].c,tp)) re+=t[now].c.cnt;
int l=ls[now],r=rs[now];
re+= query(l,tp);
re+= query(r,tp);
return re;
}
int main(){
int n=read();
while(n--){
int opt=read();
if(opt==1){
pn.x[0]=(read()^ans),pn.x[1]=(read()^ans),pn.cnt=(read()^ans);
insert(rt,pn,0);
}else if(opt==2){
q.x1=(read()^ans),q.y1=(read()^ans),q.x2=(read()^ans),q.y2=(read()^ans);
ans=query(rt,q);printf("%d\n",ans);
}else return 0;
}
return 0;
}
by Refined_heart @ 2019-12-03 22:40:38
我也是……
by Refined_heart @ 2019-12-03 22:46:59
@TLE自动机
因为不只n个操作,所以答案不够qwq
by Refined_heart @ 2019-12-03 22:47:45
刚刚自己试了,把
改成
就行了
by TLE自动机 @ 2019-12-04 10:34:29
@Refined_heart 谢大佬