萌新求助,常数被卡死了 嘤嘤嘤
查看原帖
萌新求助,常数被卡死了 嘤嘤嘤
169928
YRZ001030楼主2020/4/29 11:05

写了个树状数组套线段树 结果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
*/


2020/4/29 11:05
加载中...