191003データ構造---金華
5334 ワード
CodeForce 103 Dは長さ\(n\)の配列\(au 1,au 2,・・,aun\),\(q\)回の問い合わせを与え、毎回\(x,y,k\)を与えます.\(\\sum_{i=1}{k}a_{x+iy}を要求します.(n,m≦3×10^5,x+ky≦n\)です.ソロ:討論\(y\)の大きさは、\(\sqrt{M}\)の前処理より小さいと、暴力的になります.複雑度\(O(N\sqrt{M}\)BZOJ 2054は長さが$nのシーケンスを与えられています.$m$回の操作で、毎回操作形が\([l,r]\)を\(k\)に上書きするようになり、すべての操作後のシーケンスを求めます.\(n≦10^6、m≦10^7\).ソロ:順序を考慮して、順序を維持して検査することに対して、次の染色されていない点を表して、暴力的に守る.複雑度\(O(NlogN)\)CodeForce 480 E一つ\(n\times m\)のグリッドは、ある位置に障害物があります.\(q\)回の操作は毎回\((x,y)\)を障害物に変えて、毎回操作した後に最大のバリアフリーの正方形の大きさを聞きます.\(n,m,q≦2000\)ソロ:障害物を全部入れて一つずつ削除することを考えています.正方形の辺が長くなります.列挙の辺長、1つの点を維持して左に向って最多で何格歩くことができて、1つの障害が取り除かれた後に暴力は1行改正します.正方形が合法かどうかを確認します.単調な列で維持すればいいです.複雑度\(O(NM+qN)\)ZJOI 2016旅行者一人\(n×m\)のグリッドは、隣接する点の間に1つのエッジなしで接続されます.各辺の権利を与えます.\(q\)回の問い合わせ\((x 1,y 1)\)から$(x 2,y 2)$までの一番短絡です.\(n×m≦2×10^4,q≦10^5\)です.ソロ:治療を考えて、長方形の長い辺を選んで、中間から切り離して、線上の各点に対して一回ずつ他の各点の一番短絡をします.このように明らかにすべての問い合わせ先はこの線を通る最短の短絡を計算することができます.毎回断面の長い辺なので、長方形の長い辺の長さはきっと\(\\sqrt{S}\)より小さくて、Sは元の長方形の面積です.したがって、複雑度\(O(S\sqrt{S}logs+qlogS)\)平面の一番近い点は、与えられた平面上の$N個の点に対して、一番近い点を求めます.(1≦N≦10^5\).ソロ:ポイントを二つに分けるたびに、今は中間線を通る点を考えます.距離を\(h\)とすると、中線ぐらいの距離が\(h\)の点でしか役に立ちません.各このような点については,……毎回せいぜい「(7\)個の点だけが貢献できる.」複雑度\(O(NlogN)\)の例題は\(N\)個の点の多角形と三角断面を与えて、\(Q\)は2点を尋ねて最も短絡します.\(1≦N,Q≦10^5\).ソロ:1つを選んで切り、この2つの点を通る最短の短絡を計算し、治療していけばいいです.複雑度\(O(Nlogh{1.5}N)\)証明?BZOJ 1468は\(N\)個の点の木を与えられました.どれぐらいの対点距離があるかを求めます.\(K\)を超えません.(1≦N≦2×10^5\)ソロ:テンプレートの問題をポイントします.BZOJ 2599は、\(N\)個の点の木を与えられ、各辺には長さがあります.すべての距離が\(K\)の簡単なパスの中で、辺の数が最小でいくらですか?\(1≦N≦2×10^5,1≦K≦10^6\)です.ソロ:治療を受けるなら、前の問題よりも、長さがkの経路の一番小さい辺の数を多く記録してください.同じケケの木の中の端を二回計算しないように注意してください.もう一つの例題は、\(N\)個のポイントを与えられたツリーのどれぐらいの区間があるかを求めます.\(L、L＋1、L＋2、・・、R\)これらの点は一つの経路に対応しています.\(1≦N≦10^5\).sol:点分治は、1つの分治重心\(x\)に対して、残りのサブツリー内にルートノード番号が\(x＋1\)と\(x-1\)の点を見つけて、\(x\)を通った極長の合法的な経路を見つけて、経路長を\(len\)とすれば、\(x\)の貢献は\(len-1\)となります.三次元偏順問題は$N個の点\((xui,yui,zui)\)を与えられ、どれぐらいの対\(i,j)\)があるかを求め、以下の3つの条件を満たす.(1≦N≦2×10^5\)ソロ:板BZOJ 2683は無限大のグリッドを与えています.2つの動作:シングルポイントに1つの数を加えるか、または長方形内部の重みと合計を尋ねます.(1≦N≦2×10^5\)ソロ:時間によって治療する.BZOJ 2716保守ポイントセットは、毎回1つのポイントを追加するか、または1つのポイントからマンハッタンまでの距離が一番近いところはどれぐらいですか?(1≦N≦5×10^5\)ソロ:4回\(CDQ\)POJ 2104所与長さ\(N\)のシーケンス\(A_1,・・・A N\),\(Q\)次クエリ区間\([L,R]\)の中の第\(K\)の小さい数字.\(1≦N,Q≦2×10^5\)ソロ:テンプレートは以下の通りです.
#include
#include
#include
using namespace std;
const int N=450000;
struct node{
int l,r,cur,kn,val,d;
} q[N],q1[N],q2[N];
int n,m,ans[N],tmp[N],p[N],cnt,st[N];
inline int lowbit(int x){return x&(-x);}
void add(int x,int y){
for(int i=x;i<=cnt+1;i+=lowbit(i))
st[i]+=y;
}
int query(int x){
int num=0;
for(int i=x;i>0;i-=lowbit(i))
num+=st[i];
return num;
}
void divide(int head,int tail,int l,int r){
if(head>tail) return;
if(l==r){
for(int i=head;i<=tail;i++)
if(q[i].kn==3) ans[q[i].d]=l;
return;
}
int mid=l+r>>1;
for(int i=head;i<=tail;i++){
if(q[i].kn==1&&q[i].val<=mid) add(q[i].l,1);
else if(q[i].kn==2&&q[i].val<=mid) add(q[i].l,-1);
else if(q[i].kn==3) tmp[i]=query(q[i].r)-query(q[i].l-1);
}
for(int i=head;i<=tail;i++){
if(q[i].kn==1&&q[i].val<=mid) add(q[i].l,-1);
else if(q[i].kn==2&&q[i].val<=mid) add(q[i].l,1);
}
int x=0,y=0;
for(int i=head;i<=tail;i++){
if(q[i].kn==3){
if(q[i].cur+tmp[i]>=q[i].val) q1[++x]=q[i];
else q[i].cur+=tmp[i],q2[++y]=q[i];
}
else{
if(q[i].val<=mid) q1[++x]=q[i];
else q2[++y]=q[i];
}
}
for(int i=1;i<=x;i++) q[head+i-1]=q1[i];
for(int i=1;i<=y;i++) q[head+x+i-1]=q2[i];
divide(head,head+x-1,l,mid);
divide(head+x,tail,mid+1,r);
}
int main(){
while(cin>>n){
int t=0,maxn=0;cnt=0;
for(int i=1;i<=n;i++){
cin>>p[i];maxn=max(maxn,p[i]);
q[++cnt].kn=1;q[cnt].l=i;
q[cnt].val=p[i];q[cnt].cur=0;
}
cin>>m;
for(int i=1;i<=m;i++){
int a,b,c;cin>>a;
if(a==1){
cin>>a>>b;maxn=max(maxn,b);
q[++cnt].kn=2;q[cnt].l=a;
q[cnt].val=p[a];q[cnt].cur=0;
q[++cnt].kn=1;q[cnt].l=a;
q[cnt].val=b;q[cnt].cur=0;
p[a]=b;
}
else{
cin>>a>>b>>c;
q[++cnt].kn=3;q[cnt].l=a;
q[cnt].r=b;q[cnt].val=c;
q[cnt].cur=0;q[cnt].d=++t;
}
}
divide(1,cnt,1,maxn+1);
for(int i=1;i<=t;i++) cout<