敲日期的時候才發現今天是雙 11 11 11。。
T1 星際旅行
簽到題。
排序後 upper_bound 一下即可。
時間複雜度 O ( n log n ) O(n\log n) O(nlogn)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IO{
const int Rlen=1<<22|1;
char buf[Rlen],*p1,*p2;
inline char gc(){
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T Read(){
char c=gc();T x=0,f=1;
while(!isdigit(c)) f^=(c=='-'),c=gc();
while( isdigit(c)) x=(x+(x<<2)<<1)+(c^48),c=gc();
return f?x:-x;
}
inline int in() {return Read<int>();}
}
using IO::in;
const int N=2e5+5;
int n,S,a[N];
int main(){
n=in(),S=in();
for(int i=1;i<=n;++i) a[i]=in();
sort(a+1,a+n+1);
ll ans=0;
for(int i=1;i<=n;++i){
if(a[i]>=S) break;
int pos=upper_bound(a+1,a+i,S-a[i])-a;
ans+=pos-1;
}
printf("%lld\n",ans);
return 0;
}
T2 罔兩「栖息于禅寺的妖蝶」
考場上直接打了個表，發現答案是：
( ⌊ n + m 2 ⌋ m ) \binom{\lfloor\frac{n+m}2\rfloor}{m} (m⌊2n+m⌋)
也可以先寫一個 O ( n 2 ) O(n^2) O(n2) 的 d p dp dp 暴力，通過那個想正解。
這裡是 std 的推導：
設選出來的數從小到大是 a 1 , a 2 , ⋯ , a m a_1,a_2,\cdots,a_m a1,a2,⋯,am，考慮令 b i = a i + i b_i=a_i+i bi=ai+i。發現 b i b_i bi 全是偶數且互不相同，那麼一個 b b b 就唯一對應着一個 a a a，是以問題就變成了從 n + m n+m n+m 的偶數中選出 m m m 個的方案數。
時間複雜度 O ( T ) O(T) O(T)。
#include<bits/stdc++.h>
using namespace std;
namespace IO{
const int Rlen=1<<22|1;
char buf[Rlen],*p1,*p2;
inline char gc(){
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T Read(){
char c=gc();T x=0,f=1;
while(!isdigit(c)) f^=(c=='-'),c=gc();
while( isdigit(c)) x=(x+(x<<2)<<1)+(c^48),c=gc();
return f?x:-x;
}
inline int in() {return Read<int>();}
}
using IO::in;
const int N=2e6+5,P=998244353;
int n,m,fac[N],ifac[N];
int add(int x,int y) {return x+y>=P?x+y-P:x+y;}
int dec(int x,int y) {return x-y< 0?x-y+P:x-y;}
int mul(int x,int y) {return 1ll*x*y>=P?1ll*x*y%P:x*y;}
int power(int a,int b){
int ans=1;
for(;b;b>>=1,a=mul(a,a)) if(b&1) ans=mul(ans,a);
return ans;
}
int Inv(int x) {return power(x,P-2);}
void prework(){
fac[0]=fac[1]=1;
for(int i=2;i<N;++i) fac[i]=mul(fac[i-1],i);
ifac[N-1]=Inv(fac[N-1]);
for(int i=N-2;~i;--i) ifac[i]=mul(ifac[i+1],i+1);
}
int C(int n,int m) {return n<m?0:mul(fac[n],mul(ifac[m],ifac[n-m]));}
int main(){
prework();
int T=in();
while(T--){
n=in(),m=in();
printf("%d\n",C((n+m)>>1,m));
}
return 0;
}
T3 式神「八雲藍」
一道大力分類讨論的題。
設詢問區間是 [ x , y ] [x,y] [x,y]，對于線段樹的節點 [ l , r ] [l,r] [l,r]，相當于統計多少個 [ x , y ] [x,y] [x,y] 的子區間會影響 [ l , r ] [l,r] [l,r]。
- [ l , r ] [l,r] [l,r] 包含 [ x , y ] [x,y] [x,y]，那麼 [ x , y ] [x,y] [x,y] 的所有子區間都對 [ l , r ] [l,r] [l,r] 有貢獻。
-
[ l , r ] [l,r] [l,r] 與 [ x , y ] [x,y] [x,y] 真相交，即要排除包含關系部分，那麼又要分兩種情況（記 s u m sum sum 為 [ x , y ] [x,y] [x,y] 總區間個數）：
1. l ≤ x ≤ r ≤ y l\le x\le r\le y l≤x≤r≤y：貢獻是 s u m − ( y − r ) ( y − r + 1 ) 2 sum-\frac{(y-r)(y-r+1)}2 sum−2(y−r)(y−r+1)。
2. x ≤ l ≤ y ≤ r x\le l\le y\le r x≤l≤y≤r：貢獻是 s u m − ( l − x ) ( l − x + 1 ) 2 sum-\frac{(l-x)(l-x+1)}2 sum−2(l−x)(l−x+1)。
相當于減掉 [ x , y ] [x,y] [x,y] 中不與 [ l , r ] [l,r] [l,r] 相交的區間。
-
[ x , y ] [x,y] [x,y] 包含 [ l , r ] [l,r] [l,r]，貢獻是 s u m − ( l − x ) ( l − x + 1 ) 2 − ( y − r ) ( y − r + 1 ) 2 sum-\frac{(l-x)(l-x+1)}{2}-\frac{(y-r)(y-r+1)}{2} sum−2(l−x)(l−x+1)−2(y−r)(y−r+1)，若是非葉節點要減 2 ( l − x + 1 ) ( y − r + 1 ) 2(l-x+1)(y-r+1) 2(l−x+1)(y−r+1)。
第 1 1 1 個減的部分：排除與 [ l , r ] [l,r] [l,r] 不交的情況；
第 2 2 2 個減的部分：若若完全覆寫某個節點，那麼它的兩個兒子均不能覆寫。是以統計時要減去 ( f a l − x + 1 ) ( y − f a r + 1 ) (fa_l-x+1)(y-fa_r+1) (fal−x+1)(y−far+1)，表示完全覆寫父親的情況。這裡相當于是轉換了一下，在父親的時候統計減的貢獻，更友善一點。
發現前兩個線上段樹上隻有 O ( log n ) O(\log n) O(logn) 個點，可以暴力統計。但是情況 3 3 3 是有 O ( log n ) O(\log n) O(logn) 個子樹，暴力會 T。
如果把 x , y x,y x,y 當做未知數，情況 3 3 3 的貢獻式子會化成 A x 2 + B x y + C y 2 + D x + E y + F Ax^2+Bxy+Cy^2+Dx+Ey+F Ax2+Bxy+Cy2+Dx+Ey+F 的形式，可以線上段樹上維護這些系數，把子樹的答案都加到父親上來，統計的時候把 x , y x,y x,y 具體的值代進去即可。
時間複雜度 O ( q log n ) O(q\log n) O(qlogn)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IO{
const int Rlen=1<<22|1;
char buf[Rlen],*p1,*p2;
inline char gc(){
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T Read(){
char c=gc();T x=0,f=1;
while(!isdigit(c)) f^=(c=='-'),c=gc();
while( isdigit(c)) x=(x+(x<<2)<<1)+(c^48),c=gc();
return f?x:-x;
}
inline int gi() {return Read<int>();}
inline ll gl() {return Read<ll >();}
}
using IO::gi;
using IO::gl;
const int N=5e5+5;
int n,q,op;
ll l,r,sum,last=0;
namespace SGT{
struct Seg{ll sze,B,D,E,F;}T[N<<2];
void pushup(int root){
T[root].B+=T[root<<1].B+T[root<<1|1].B;
T[root].D+=T[root<<1].D+T[root<<1|1].D;
T[root].E+=T[root<<1].E+T[root<<1|1].E;
T[root].F+=T[root<<1].F+T[root<<1|1].F;
T[root].sze+=T[root<<1].sze+T[root<<1|1].sze;
}
#define mid ((l+r)>>1)
void build(int root,int l,int r){
T[root].sze=1;
T[root].D=2*l+1,T[root].E=2*r-1,T[root].F=-(ll)l*l-(ll)r*r-l+r;
if(l==r) return;
build(root<<1,l,mid),build(root<<1|1,mid+1,r);
T[root].B+=4,T[root].D+=-4*r+4,T[root].E+=-4*l-4,T[root].F+=4ll*l*r-4*l+4*r-4;
pushup(root);
}
ll Query(int root,int l,int r,int x,int y){
if(l>=x&&r<=y){
ll ans=0;
ans+=(T[root].B*x*y+T[root].D*x+T[root].E*y+T[root].F+(sum-(ll)x*x-(ll)y*y)*T[root].sze);
return ans;
}
ll ans=sum;
if(l>=x) ans-=(ll)(l-x)*(l-x+1);
if(r<=y) ans-=(ll)(y-r)*(y-r+1);
if(x<=mid) ans+=Query(root<<1,l,mid,x,y);
if(y> mid) ans+=Query(root<<1|1,mid+1,r,x,y);
return ans;
}
#undef mid
}
void Get(ll &l,ll &r){
l=(gl()^(last*op))%n+1,r=(gl()^(last*op))%n+1;
if(l>r) swap(l,r);
}
int main(){
n=gi(),q=gi(),op=gi();
SGT::build(1,1,n);
while(q--){
Get(l,r),sum=(ll)(r-l+1)*(r-l+2);
printf("%lld\n",last=SGT::Query(1,1,n,l,r)/2);
}
return 0;
}