http://acm.hdu.edu.cn/showproblem.php?pid=6315
In a galaxy far, far away, there are two integer sequence $a$ and $b$ of length $n$.
$b$ is a static permutation of $1$ to $n$. Initially a is filled with zeroes.
There are two kind of operations:
1. add l r: add one for $a_l,a_{l+1}\dots a_r$
2. query l r: query $\sum_{i=l}^r\lfloor ai/bi \rfloor$
There are multiple test cases, please read till the end of input file.
For each test case, in the first line, two integers n,q, representing the length of a,b and the number of queries.
In the second line, n integers separated by spaces, representing permutation b.
In the following q lines, each line is either in the form 'add l r' or 'query l r', representing an operation.
$1 \leqslant n,q \leqslant 100000, 1 \leqslant l \leqslant r\leqslant n$, there're no more than 5 test cases.
Output the answer for each 'query', each one line.
其实根本不会做……
$\lfloor a/b \rfloor = \frac{a-a\%b}{b}$，记录$a$和$a\%b$比较麻烦，因此记录$\frac{a-a\%b}{b}=\boldsymbol{v}$和$a\%b=\boldsymbol{b}$(我就喜欢乱用符号= =)
那么只需某处$\boldsymbol{b}=0$就将v单点修改+1，容易用线段树写出来……（注意可能同时有多个地方=0）
因为$n,q \leqslant 100000$，b又是一个1～n的排列，所以所有和小于$\sum_{i=1}^n\frac{n}{i}=n(\ln{n}+\gamma+\frac{1}{2n})\approx n\ln{n}<10^8$，所以可以用int存
但是为了确定某处的$\boldsymbol{b}$，直接暴力$q\times2n>10^9$肯定超时，因此需要技巧……
因为并不是所有的$\boldsymbol{b}$每时每刻都为0，所以还需要点技巧，将$\boldsymbol{b}$设为$b-a\%b$，所以只需要关心最小的那个$\boldsymbol{b}$，同样可以用线段树维护（+区间），每次维护$\log{n}$
加起来$\mathcal{O}(n\log{n})$
查询的时候并不需要向下和向上更新
还要注意更新延迟变量$\text{d}\boldsymbol{b}$时不要写成等号= =
AC代码
#include<cstdio> #include<cstdlib> #include<cctype> #include<cstring> #include<algorithm> #include<set> #define REP(r,x,y) for(register int r=(x); r<(y); r++) #define REPE(r,x,y) for(register int r=(x); r<=(y); r++) #define PERE(r,x,y) for(register int r=(x); r>=(y); r--) #ifdef sahdsg #define DBG(...) printf(__VA_ARGS__),fflush(stdout) #else #define DBG(...) (void)0 #endif using namespace std; typedef long long LL; typedef unsigned long long ULL; char ch; int si; char buf[1<<21],*p1=buf,*p2=buf; int beof = 0; #define gc() (beof?EOF:(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(beof=EOF):*p1++)) template<class T> inline void read(T &x) { x=0; si=1; for(ch=gc();!isdigit(ch) && ch!='-';ch=gc()) if(beof) return; if(ch=='-'){si=-1,ch=gc();} for(;isdigit(ch);ch=gc())x=x*10+ch-'0'; x*=si; } //template<class T, class...A> inline void read(T &x, A&...a){read(x); read(a...);} #define MAXN 100007 int b[MAXN]; struct node { int v,b,db; int l,r; } st[MAXN*4]; inline void st0(int p, int l, int r) { st[p].l=l, st[p].r=r, st[p].v=st[p].db=0; if(l==r) { st[p].b=b[l]; return; } int m=(l+r)>>1; st0(p*2,l,m); st0(p*2+1,m+1,r); st[p].b=min(st[p*2].b,st[p*2+1].b); } inline void spreadb(int p) { if(st[p].db) { st[p*2].db+=st[p].db; st[p*2].b-=st[p].db; st[p*2+1].db+=st[p].db; st[p*2+1].b-=st[p].db; st[p].db=0; } } inline void op_C(int p) { if(st[p].l==st[p].r) { st[p].v++; st[p].b=b[st[p].l]; return; } spreadb(p); if(!st[p*2].b) op_C(p*2); if(!st[p*2+1].b) op_C(p*2+1); st[p].v=st[p*2].v+st[p*2+1].v; st[p].b=min(st[p*2].b, st[p*2+1].b); } inline void opA(int p, int l, int r) { if(l<=st[p].l && r>=st[p].r) { st[p].b--; st[p].db++; if(st[p].b==0) { op_C(p); } return; } spreadb(p); int m=(st[p].l+st[p].r)>>1; if(l<=m) opA(p*2,l,r); if(r>m) opA(p*2+1,l,r); st[p].v=st[p*2].v+st[p*2+1].v; st[p].b=min(st[p*2].b, st[p*2+1].b); } inline int opQ(int p, int l, int r) { if(l<=st[p].l && r>=st[p].r) { return st[p].v; } int m=(st[p].l+st[p].r)>>1; int ans=0; if(l<=m) ans+=opQ(p*2,l,r); if(r>m) ans+=opQ(p*2+1,l,r); return ans; } int main() { #ifdef sahdsg freopen("in.txt","r",stdin); #endif int n,q; read(n);read(q); while(!beof) { REPE(i,1,n) read(b[i]); st0(1,1,n); while(0<q--) { char k; do k=gc(); while(isspace(k)); int l,r; read(l); read(r); if(k=='a') opA(1,l,r); else printf("%d\n", opQ(1,l,r)); } read(n); read(q); } return 0; }
转载于:https://www.cnblogs.com/sahdsg/p/10828831.html
相关资源：JAVA上百实例源码以及开源项目