有一棵这样的线段树： mid不再等于(l+r)/2，而是l~r中的某个数，（代表什么呢，这棵树不是lgn级别的）…..询问区间中完整区间的个数
分析： 可以转化为区间计数问题 用区间长度为1的区间个数减去所有区间长度不为1的区间个数 可以用树状数组维护： 把询问按照l从大到小排序，然后查询r的个数
代码如下：
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; const int maxn=100000+5; int n,m,hd[maxn],to[maxn],nxt[maxn],cnt,tree[maxn],ans[maxn]; struct lala{ int l,r,index; friend bool operator < (lala a,lala b){ return a.l<b.l; } }s[maxn]; inline void add(int x,int y){ to[cnt]=y; nxt[cnt]=hd[x]; hd[x]=cnt++; } inline void build(int l,int r){ if(l==r) return; int mid; add(l,r); scanf("%d",&mid); build(l,mid),build(mid+1,r); } inline void insert(int x,int y){ for(;x<=n;x+=(x&(-x))) tree[x]+=y; } inline int query(int x){ int sum=0; for(;x;x-=(x&(-x))) sum+=tree[x]; return sum; } signed main(void){ scanf("%d%d",&n,&m); memset(hd,-1,sizeof(hd)),cnt=0; build(1,n); for(int i=1;i<=m;i++){ s[i].index=i; scanf("%d%d",&s[i].l,&s[i].r); } sort(s+1,s+m+1); for(int i=n,k=m;i>=1;i--){ for(int j=hd[i];j!=-1;j=nxt[j]) insert(to[j],1); while(s[k].l==i) ans[s[k].index]=s[k].r-s[k].l+1-query(s[k].r),k--; } for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; }by >_< neighthorn
