泸州中泸集团建设有限公司网站,湖北省住房和城乡建设部门户网站,建设网站技术标准,如何建设社区网站洛谷
题意#xff1a; 思路#xff1a; 考虑整体二分前#xff0c;一定要思考一下直接二分怎么做。显然对每个城市#xff0c;当pospospos的时候收集不够足够的陨石#xff0c;pospospos的时候能收集足够多陨石#xff0c;这个时候pospospos即…洛谷
题意 思路 考虑整体二分前一定要思考一下直接二分怎么做。显然对每个城市当pospospos的时候收集不够足够的陨石pospospos的时候能收集足够多陨石这个时候pospospos即为答案。这显然具有二分性复杂度为O(NMlogM)O(NMlogM)O(NMlogM)。让后我们发现可以将所有城市放在一起二分假设当前陨石落下波数区间为[l,r][l,r][l,r]midlr1midlr1midlr1当前面[l,mid][l,mid][l,mid]陨石落下来的时候就足达到个城镇的预期的话就把这个城镇放在左边否则放在右边。让后将[l,mid][l,mid][l,mid]跟放在左边的城镇递归下去[mid1,r][mid1,r][mid1,r]跟放在右边的城镇递归下去。最终lrlrlr的时候更新答案即可。 有可能存在无解的情况我们只需要把初始的[1,k][1,k][1,k]改成[l,k1][l,k1][l,k1]等于k1k1k1的时候无解。 还有一个要注意的点是代码的86行加到期望之后要停下来不然可能会爆LL因为这个调了一下午。 区间加单点查询用树状数组应该不用多说了用线段树可能会T。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
#define lowbit(x) ((x)(-x))
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N300010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m,k;
LL s[N];
int p[N],p1[N],p2[N],ans[N];
struct Query
{LL l,r,c,id;
}q[N];
vectorintv[N];
LL tr[N2];void add(int x,LL c)
{for(int ix;im*2;ilowbit(i)) tr[i]c;
}LL sum(int x)
{LL ans0;for(int ix;i;i-lowbit(i)) anstr[i];return ans;
}void solve(int l,int r,LL c)
{if(lr) add(l,c),add(r1,-c);else add(r,c),add(m1,-c),add(1,c),add(l1,-c);
}void solve(int l,int r,int begin,int end)
{int midlr1;if(lr){for(int ibegin;iend;i){int idp[i];ans[id]l;}return;}for(int il;imid;i) add(q[i].l,q[i].c),add(q[i].r1,-q[i].c);int cnt1,cnt2; cnt1cnt20;for(int ibegin;iend;i){int idp[i];LL ssum0;for(int j0;jv[id].size()ssums[id];j) ssumsum(v[id][j])sum(v[id][j]m);if(ssums[id]) p1[cnt1]p[i];else p2[cnt2]p[i],s[id]-ssum;}for(int il;imid;i) add(q[i].l,-q[i].c),add(q[i].r1,q[i].c);for(int i1;icnt1;i) p[begini-1]p1[i];for(int i1;icnt2;i) p[begincnt1i-1]p2[i];solve(l,mid,begin,begincnt1-1); solve(mid1,r,begincnt1,end);
}template class T
bool read(T ret)//输入
{char c;int sgn;T bit0.1;if(cgetchar(), cEOF)return 0;while(c!- c!. (c0 || c9))cgetchar();sgn(c-)? -1:1;ret(c-)? 0:(c-0);while(cgetchar(), c0 c9)retret*10(c-0);if(c || c\n){ret*sgn;return 1;}while(cgetchar(), c0 c9)ret(c-0)*bit, bit/10;ret*sgn;return 1;
}inline void out(int x)//输出
{if(x9)out(x/10);putchar(x%100);
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);read(n); read(m);for(int i1;im;i){int x; read(x);v[x].pb(i);}for(int i1;in;i) p[i]i;for(int i1;in;i) read(s[i]);read(k);for(int i1;ik;i){int l,r,c; read(l); read(r); read(c);if(lr) rm;q[i]{l,r,c,i};}solve(1,k1,1,n);for(int i1;in;i) (ans[i]k1)? puts(NIE):printf(%d\n,ans[i]);return 0;
}
/**/
