写了个树状数组套线段树 结果o2+快读都拯救不了我的时间 第一个点和第七个点卡的死死的。求聚聚拯救下
#include"stdio.h"
#include"string.h"
#include"stack"
#include"map"
#include"math.h"
#include"iostream"
#include"vector"
#include"queue"
#include"algorithm"
using namespace std;
#define OK printf("\n");
#define Debug printf("this_ok\n");
#define inf 1e9
#define INF 1e18
typedef long long ll;
#define scanll(a,b) scanf("%lld%lld",&a,&b);
#define scanl(a) scanf("%lld",&a);
#define printl(a,b) if(b == 0) printf("%lld ",a); else printf("%lld\n",a);
#define print_int(a,b) if(b == 0) printf("%d ",a); else printf("%d\n",a);
typedef pair<int,int> PII;
#define Finline __inline__ __attribute__ ((always_inline))
Finline char get_char()
{
static char buf[200000001], *p1 = buf, *p2 = buf + fread(buf, 1, 200000000, stdin);
return p1 == p2 ? EOF : *p1 ++;
}
inline int read(){
int num = 0;
char c;
while((c = get_char()) < 48);
while(num = num * 10 + c - 48, (c = get_char()) >= 48);
return num;
}
const ll mod = 998244353;
const int N = 300000;
const double pi = acos(-1);
typedef struct Node{
int a,b; Node(){}
Node(int x,int y){
a = x; b = y;
}
}Node;
int n,m;
int root[N << 5],sum[N << 5],lc[N << 5],rc[N << 5],tot;
int k,res[N],X_a[N],X_b[N],X_top,lenx;
int Y_a[N],Y_b[N],Y_top,leny;
int val1[N * 100],val2[N * 100];
Node node[N];
int lowbit(int x){
return x & (-x);
}
int cmp(Node a,Node b){
if(a.a != b.a) return a.a < b.a;
return a.b < b.b;
}
int is_equal(Node a,Node b){
if(a.a == b.a && a.b == b.b) return 1;
return 0;
}
void update(int &rt,int L,int R,int pos,int val){
if(rt == 0) rt = ++ tot;
if(L == R) {
sum[rt] += val;
return ;
}
int mid = (L + R) >> 1;
if(pos <= mid) update(lc[rt],L,mid,pos,val);
else update(rc[rt],mid + 1,R,pos,val);
sum[rt] = sum[lc[rt]] + sum[rc[rt]];
}
void Update(int x,int pos,int cnt){
for(int i = x; i <= lenx; i += lowbit(i)){
update(root[i],1,leny,pos,cnt);
}
}
int query(int rt,int L,int R,int l,int r){
if(l <= L && r >= R){
return sum[rt];
}
int mid = (L + R) >> 1,ans = 0;
if(l <= mid) ans += query(lc[rt],L,mid,l,r);
if(r > mid) ans += query(rc[rt],mid + 1,R,l,r);
return ans;
}
int getsum(int x,int l,int r){
int res = 0;
for(int i = x; i > 0; i -= lowbit(i)){
res += query(root[i],1,leny,l,r);
}
return res;
}
int main()
{
n = read(); int q = read();
for(int i = 1; i <= n; i ++){
node[i].a = read(); node[i].b = read();
X_a[++ X_top] = node[i].a;X_b[X_top] = X_a[X_top];
Y_a[++ Y_top] = node[i].b;Y_b[Y_top] = Y_a[Y_top];
}
sort(node + 1,node + n + 1,cmp);
sort(X_b + 1,X_b + X_top + 1); lenx = unique(X_b + 1,X_b + X_top + 1) - X_b - 1;
sort(Y_b + 1,Y_b + Y_top + 1); leny = unique(Y_b + 1,Y_b + Y_top + 1) - Y_b - 1;
int cnt = 1;
for(int i = 1; i <= n; i ++){
if(i + 1 <= n && is_equal(node[i],node[i + 1])) {cnt ++; continue;}
int x = lower_bound(X_b + 1,X_b + lenx + 1,node[i].a) - X_b;
int y = lower_bound(Y_b + 1,Y_b + leny + 1,node[i].b) - Y_b;
Update(x,y,cnt);
cnt = 1;
}
while(q --){
int a = read(),b = read(),c = read(),d = read();
int a1 = lower_bound(X_b + 1,X_b + lenx + 1,a) - X_b - 1;
int c1 = lower_bound(X_b + 1,X_b + lenx + 1,c) - X_b;
if(c1 > lenx || X_b[c1] != c) c1 --;
int b1 = lower_bound(Y_b + 1,Y_b + leny + 1,b) - Y_b;
int d1 = lower_bound(Y_b + 1,Y_b + leny + 1,d) - Y_b;
// printf("d1 = %d leny = %d Y_b[da] = %d\n",d1,leny,Y_b[d1]);
if(d1 > leny || Y_b[d1] > d) d1 --;
int ans1 = getsum(a1,b1,d1);
int ans2 = getsum(c1,b1,d1);
// printf("a1 = %d b1 = %d c1 = %d d1 = %d ans1 = %d ans2 = %d\n",a1,b1,c1,d1,ans1,ans2);
printf("%d\n",ans2 - ans1);
}
}
/*
3 10
0 0
0 1
1 0
1 1 1 1
0 0 1 0
*/