突然想到的节约时间的方法，感觉6翻了
给你n个数字，接着m个询问。每次问你一段区间内不大于某个数字（不一定是给你的数字）的个数
直接线段树没法做，因为每次给你的数字不一样，父节点无法统计。但是离线一下，如果后面的询问可以用前面已经处理过的一些东西，则可以节约时间。换句话说，就是直接把给数字z进行从小到大排序，每次暴力更新数字a小于等于数字z的叶子节点，数字a赋值为极大值，这样前面更新了的数字a在后面就不需要再更新了，而且后面的数字z一定不小于前面更新了的数字a，而且总数一共最多更新n次
做了这么一些线段树有一些心得就是：有时看似区间内部复杂得无法统计的东西，其实从叶子节点开始，两个两个合并在一起就可以解决的话，则只需要每次处理上下更新就可以处理整棵树了，但是注意这儿有孩子节点只影响父亲节点这个条件
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<30; const double Pi=acos(-1.0); const int Max=100010<<2; const int Mod=10; struct node { int minx,sum;//区间最小值 区间-1的个数（-1代表叶子没有这个值） }segtr[Max]; struct nide { int lef,rig,hei,pos; }qes[Max]; int nmin(int a,int b) { return a>b?b:a; } void Upnow(int now,int next) { segtr[now].sum=segtr[next].sum+segtr[next|1].sum; segtr[now].minx=nmin(segtr[next].minx,segtr[next|1].minx); return; } void Create(int sta,int enn,int now) { if(sta==enn) { segtr[now].sum=0; scanf("%d",&segtr[now].minx); return; } int mid=dir(sta+enn,1); int next=mul(now,1); Create(sta,mid,next); Create(mid+1,enn,next|1); Upnow(now,next); return; } bool cmp(struct nide p1,struct nide p2) { return p1.hei<p2.hei;//关键 从小到大 } int ans[Max]; int Query(int sta,int enn,int now,int x,int y,int z) { if(sta>=x&&enn<=y) { if(segtr[now].minx>z)//此区间没有值大于z return segtr[now].sum;//注意这儿之前删除的叶子一定是大于等于z的（排序的原因） else if(sta==enn)//是叶子就更新回溯，不是的话就继续递归下去 { segtr[now].minx=Inf;//赋值为极大值，则一定不z大 segtr[now].sum=1; return 1; } } int mid=dir(sta+enn,1); int next=mul(now,1); int ans=0; if(mid>=x) ans+=Query(sta,mid,next,x,y,z); if(mid<y) ans+=Query(mid+1,enn,next|1,x,y,z); Upnow(now,next); return ans; } int main() { int t,n,q,coun=0; scanf("%d",&t); while(t--) { scanf("%d %d",&n,&q); Create(1,n,1); for(int i=0;i<q;i++) { scanf("%d %d %d",&qes[i].lef,&qes[i].rig,&qes[i].hei); qes[i].pos=i; qes[i].lef++,qes[i].rig++; } sort(qes,qes+q,cmp);//按照hei从小到大，前面的更新了线段树，后面就可以继续用 for(int i=0;i<q;i++) ans[qes[i].pos]=Query(1,n,1,qes[i].lef,qes[i].rig,qes[i].hei);//离线统计 printf("Case %d: ",++coun); for(int i=0;i<q;i++) printf("%d ",ans[i]); } return 0; }