招商网站建设,做网站加一个定位功能要多少钱,什么是网络营销中的免费营销策略,张家港做网站排名题目链接#xff1a;D. Frets On Fire 思路#xff1a;明明可以离散化二分写#xff0c;思路硬是歪到了线段树上#xff0c;自闭了#xff0c;真实弟弟#xff0c;怪不得其他人过得那么快 只和查询的区间长度有关系#xff0c;排完序如果相邻的两个点的差值小于等于查询…题目链接D. Frets On Fire 思路明明可以离散化二分写思路硬是歪到了线段树上自闭了真实弟弟怪不得其他人过得那么快 只和查询的区间长度有关系排完序如果相邻的两个点的差值小于等于查询的区间长度那么给结果带来的变化就会新增差值个数如果大于区间长度那么就会新增区间长度个数 维护的话线段树和二分都可以二分需要离散化处理再给差值排个序每次找到第一个大于当前区间长度的差值位置就好了没实现但是理论上应该没问题 线段树直接动态开点可以不用离散化。。 实现代码 #includebits/stdc.h
using namespace std;
typedef long long ll;
#define mid ll m (l r) /2
const ll M 1e510;
#define ROF(i,a,b) for(ll ia;ib;i--)
ll sum[M*40],num[M*40];
ll ls[M*40],rs[M*40];
ll idx;
void update(ll p,ll c,ll l,ll r,ll rt){if(!rt) rt idx;sum[rt] c;num[rt] 1;if(l r){return ;}mid;if(p m) update(p,c,l,m,ls[rt]);else update(p,c,m1,r,rs[rt]);
}ll query(ll L,ll R,ll l,ll r,ll rt){if(L lR r){return sum[rt];}mid;ll ret 0;if(L m) ret query(L,R,l,m,ls[rt]);if(R m) ret query(L,R,m1,r,rs[rt]);return ret;
}ll ask(ll L,ll R,ll l,ll r,int rt){if(L lR r){return num[rt];}mid;ll ret 0;if(L m) ret ask(L,R,l,m,ls[rt]);if(R m) ret ask(L,R,m1,r,rs[rt]);return ret;
}
ll a[2*M];
int main()
{ll n,m,x,y,rt 0;scanf(%lld,n);for(ll i 1;i n;i ){scanf(%lld,a[i]);}sort(a1,a1n);for(ll i 2;i n;i ){ll num a[i] - a[i-1];update(num,num,1,1e18,rt);}scanf(%lld,m);for(ll i 1;i m;i ){scanf(%lld%lld,x,y);ll num y-x1;ll ans num;ans query(1,num,1,1e18,rt);//coutans ;ans ask(num1,1e18,1,1e18,rt)*num;printf(%lld\n,ans);}
} 转载于:https://www.cnblogs.com/kls123/p/10663399.html
