#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
const int MAX_N = 103;
vector<int> edg[MAX_N];
bool visit[MAX_N];
int who_get_stamp[MAX_N];
void dfs_for_stamp(int now,int &cur_stamp) {
visit[now]=true;
int len=edg[now].size();
for (int x=0;len>x;x++) {
int j=edg[now][x];
if (visit[j]==false) dfs_for_stamp(j,cur_stamp);
}
who_get_stamp[cur_stamp++]=now;
}
int main () {
int n,m;
while (scanf("%d %d",&n,&m) != EOF) {
if (!n&&!m) return 0;
for (int x=0;n>=x;x++) edg[x].clear();
while (m--) {
int i,j;
scanf("%d %d",&i,&j);
edg[i].push_back(j);
}
for (int x=0;n>=x;x++) visit[x]=false;
int stamp=0;
for (int x=1;n>=x;x++) {
if (visit[x]==false) {
dfs_for_stamp(x,stamp);
}
}
for (int x=n-1;x>=0;x--) {
if (x!=n-1) printf(" ");
printf("%d",who_get_stamp[x]);
}
puts("");
}
}
2016年3月22日 星期二
2016年3月16日 星期三
Treap 模板(lazy tag)
http://poj.org/problem?id=3468
http://judge.ioicamp.org/problems/23
要小心的push部分XDDD
#include <iostream>
#include <stdio.h>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long LL;
struct Treap {
Treap *lc;
Treap *rc;
LL val,pri,key;
LL tag;
LL sum;
int son; //include 自己
Treap(LL _val,LL _key) {
val=_val;
key=_key;
sum=_val;
pri=rand();
tag=0;
son=1;
lc = rc = NULL;
}
};
LL sm(Treap* t) {
return t? t->sum : 0;
}
int sn(Treap* t) {
return t? t->son : 0;
}
void pull(Treap* t) {
t->sum = sm(t->lc) + sm(t->rc) + t->val;
t->son = sn(t->lc) + sn(t->rc) + 1;
}
void push(Treap* t) {
if (t->tag==0) return;
t->val += t->tag;
t->sum += t->tag;
if (t->lc) {
t->lc->tag += t->tag;
t->lc->sum += t->tag * (sn(t->lc));
}
if (t->rc) {
t->rc->tag += t->tag;
t->rc->sum += t->tag * (sn(t->rc));
}
t->tag = 0;
}
Treap* merge(Treap *a,Treap *b) {
if (!a || !b) return a?a:b;
if (a->pri > b->pri) {
push(a);
a->rc=merge(a->rc,b);
pull(a);
return a;
}
else {
push(b);
b->lc=merge(a,b->lc);
pull(b);
return b;
}
}
void split(Treap* t, int x,Treap* &a, Treap* &b) {
if (!t) a = b = NULL;
else if (t->key<=x) {
a=t;
push(a);
split(t->rc,x,a->rc,b);
pull(a);
}
else {
b=t;
push(b);
split(t->lc,x,a,b->lc);
pull(b);
}
}
LL query(Treap *t,int l,int r) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
LL ret=sm(t);
t=merge(merge(tl,t),tr);
return ret;
}
void modify(Treap* t,int l,int r,LL v) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
t->tag += v;
t->sum += v * sn(t); //沒加自己!!!
t=merge(merge(tl,t),tr);
}
int main () {
srand(time(NULL));
int T;
scanf("%d",&T);
while (T--) {
Treap* root;
root=NULL;
int n,q,i;
scanf("%d %d",&n,&q);
for (int x=1;n>=x;x++) {
scanf("%d",&i);
root=merge(root,new Treap(i,x));
// cout<<"sum = "<<root->sum<<endl;
// cout<<"val = "<<root->val<<endl;
}
while (q--) {
string d;
cin >> d;
if (d=="query") {
int i,j;
scanf("%d %d",&i,&j);
printf("%lld\n",query(root,i,j));
}
else if (d=="add"){
int i,j,k;
scanf("%d %d %d",&i,&j,&k);
modify(root,i,j,k);
}
}
// cout<<"List : ";
// for (int x=1;n>=x;x++) cout<<query(root,x,x)<<' ';
// cout<<endl;
}
}
http://judge.ioicamp.org/problems/23
要小心的push部分XDDD
#include <iostream>
#include <stdio.h>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long LL;
struct Treap {
Treap *lc;
Treap *rc;
LL val,pri,key;
LL tag;
LL sum;
int son; //include 自己
Treap(LL _val,LL _key) {
val=_val;
key=_key;
sum=_val;
pri=rand();
tag=0;
son=1;
lc = rc = NULL;
}
};
LL sm(Treap* t) {
return t? t->sum : 0;
}
int sn(Treap* t) {
return t? t->son : 0;
}
void pull(Treap* t) {
t->sum = sm(t->lc) + sm(t->rc) + t->val;
t->son = sn(t->lc) + sn(t->rc) + 1;
}
void push(Treap* t) {
if (t->tag==0) return;
t->val += t->tag;
t->sum += t->tag;
if (t->lc) {
t->lc->tag += t->tag;
t->lc->sum += t->tag * (sn(t->lc));
}
if (t->rc) {
t->rc->tag += t->tag;
t->rc->sum += t->tag * (sn(t->rc));
}
t->tag = 0;
}
Treap* merge(Treap *a,Treap *b) {
if (!a || !b) return a?a:b;
if (a->pri > b->pri) {
push(a);
a->rc=merge(a->rc,b);
pull(a);
return a;
}
else {
push(b);
b->lc=merge(a,b->lc);
pull(b);
return b;
}
}
void split(Treap* t, int x,Treap* &a, Treap* &b) {
if (!t) a = b = NULL;
else if (t->key<=x) {
a=t;
push(a);
split(t->rc,x,a->rc,b);
pull(a);
}
else {
b=t;
push(b);
split(t->lc,x,a,b->lc);
pull(b);
}
}
LL query(Treap *t,int l,int r) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
LL ret=sm(t);
t=merge(merge(tl,t),tr);
return ret;
}
void modify(Treap* t,int l,int r,LL v) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
t->tag += v;
t->sum += v * sn(t); //沒加自己!!!
t=merge(merge(tl,t),tr);
}
int main () {
srand(time(NULL));
int T;
scanf("%d",&T);
while (T--) {
Treap* root;
root=NULL;
int n,q,i;
scanf("%d %d",&n,&q);
for (int x=1;n>=x;x++) {
scanf("%d",&i);
root=merge(root,new Treap(i,x));
// cout<<"sum = "<<root->sum<<endl;
// cout<<"val = "<<root->val<<endl;
}
while (q--) {
string d;
cin >> d;
if (d=="query") {
int i,j;
scanf("%d %d",&i,&j);
printf("%lld\n",query(root,i,j));
}
else if (d=="add"){
int i,j,k;
scanf("%d %d %d",&i,&j,&k);
modify(root,i,j,k);
}
}
// cout<<"List : ";
// for (int x=1;n>=x;x++) cout<<query(root,x,x)<<' ';
// cout<<endl;
}
}
Treap 模板 (一般)
目前是沒有LAZY TAG的
http://zerojudge.tw/ShowProblem?problemid=d539
#include <iostream>
#include <stdio.h>
#include <ctime>
#include <cstdlib>
using namespace std;
const int INF = 1000000000;
struct Treap {
Treap *lc;
Treap *rc;
int val,pri,key;
int add;
int mx;
Treap(int _val,int _key) {
val=_val;
key=_key;
mx=val;
pri=rand();
add=0;
lc = rc = NULL;
}
};
int mx(Treap* t) {
return t? t->mx + t->add : -INF;
}
void pull(Treap* t) {
t->mx= max(t->val, max(mx(t->lc), mx(t->rc)) );
}
void push(Treap* t) {
t->val += t->add;
if (t->lc) t->lc->add += t->add;
if (t->rc) t->rc->add += t->add;
t->add = 0;
}
Treap* merge(Treap *a,Treap *b) {
// puts("in0");
if (!a || !b) return a?a:b;
if (a->pri > b->pri) {
push(a);
// puts("in1");
// cout<<"a->val = "<<a->val<<endl;
a->rc=merge(a->rc,b);
pull(a);
return a;
}
else {
push(b);
// puts("in2");
// cout<<"b->val = "<<b->val<<endl;
b->lc=merge(a,b->lc);
pull(b);
return b;
}
}
void split(Treap* t, int x,Treap* &a, Treap* &b) {
if (!t) a = b = NULL;
else if (t->key<=x) {
a=t;
push(a);
split(t->rc,x,a->rc,b);
pull(a);
}
else {
b=t;
push(b);
split(t->lc,x,a,b->lc);
pull(b);
}
}
int rmq(Treap *t,int l,int r) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
// puts("in");
int ret=mx(t);
t=merge(merge(tl,t),tr);
return ret;
}
void add(Treap* t,int l,int r,int v) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
t->add += v;
t=merge(merge(tl,t),tr);
}
int main () {
srand(time(NULL));
int n;
while (scanf("%d",&n) != EOF) {
Treap* root;
root=NULL;
for (int x=1;n>=x;x++) {
int i;
scanf("%d",&i);
root = merge(root,new Treap(i,x));
}
int q;
scanf("%d",&q);
while (q--) {
int i,j;
scanf("%d %d",&i,&j);
if (i>j) swap(i,j);
printf("%d\n",rmq(root,i,j));
}
}
}
http://zerojudge.tw/ShowProblem?problemid=d539
#include <iostream>
#include <stdio.h>
#include <ctime>
#include <cstdlib>
using namespace std;
const int INF = 1000000000;
struct Treap {
Treap *lc;
Treap *rc;
int val,pri,key;
int add;
int mx;
Treap(int _val,int _key) {
val=_val;
key=_key;
mx=val;
pri=rand();
add=0;
lc = rc = NULL;
}
};
int mx(Treap* t) {
return t? t->mx + t->add : -INF;
}
void pull(Treap* t) {
t->mx= max(t->val, max(mx(t->lc), mx(t->rc)) );
}
void push(Treap* t) {
t->val += t->add;
if (t->lc) t->lc->add += t->add;
if (t->rc) t->rc->add += t->add;
t->add = 0;
}
Treap* merge(Treap *a,Treap *b) {
// puts("in0");
if (!a || !b) return a?a:b;
if (a->pri > b->pri) {
push(a);
// puts("in1");
// cout<<"a->val = "<<a->val<<endl;
a->rc=merge(a->rc,b);
pull(a);
return a;
}
else {
push(b);
// puts("in2");
// cout<<"b->val = "<<b->val<<endl;
b->lc=merge(a,b->lc);
pull(b);
return b;
}
}
void split(Treap* t, int x,Treap* &a, Treap* &b) {
if (!t) a = b = NULL;
else if (t->key<=x) {
a=t;
push(a);
split(t->rc,x,a->rc,b);
pull(a);
}
else {
b=t;
push(b);
split(t->lc,x,a,b->lc);
pull(b);
}
}
int rmq(Treap *t,int l,int r) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
// puts("in");
int ret=mx(t);
t=merge(merge(tl,t),tr);
return ret;
}
void add(Treap* t,int l,int r,int v) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
t->add += v;
t=merge(merge(tl,t),tr);
}
int main () {
srand(time(NULL));
int n;
while (scanf("%d",&n) != EOF) {
Treap* root;
root=NULL;
for (int x=1;n>=x;x++) {
int i;
scanf("%d",&i);
root = merge(root,new Treap(i,x));
}
int q;
scanf("%d",&q);
while (q--) {
int i,j;
scanf("%d %d",&i,&j);
if (i>j) swap(i,j);
printf("%d\n",rmq(root,i,j));
}
}
}
(IOIcamp_Judge) 27. 骨牌 [SCC]
http://judge.ioicamp.org/problems/29
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2499
Zj上面也有
就是你要把SCC壓成一個點，然後不斷去找入度=0的點，就好了
求SCC：
1. 把圖反向
2. topological sort反向圖，紀錄time tag
3. 從time tag最大的開始dfs SCC
這裡 是另外一邊一模一樣的
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2499
Zj上面也有
就是你要把SCC壓成一個點，然後不斷去找入度=0的點，就好了
求SCC：
1. 把圖反向
2. topological sort反向圖，紀錄time tag
3. 從time tag最大的開始dfs SCC
這裡 是另外一邊一模一樣的
#include <iostream> #include <algorithm> #include <vector> #include <cstring> #include <stdio.h> using namespace std; const int MAX_N = 100003; vector<int> edg[MAX_N]; vector<int> rev_edg[MAX_N]; bool visit[MAX_N]; int who_get_stamp[MAX_N]; int in_scc[MAX_N]; vector<int> sccedg[MAX_N]; int rudu[MAX_N]; int chudu[MAX_N]; void dfs_for_stamp(int now,int& cur_stamp) { // cout<<"in "<<now<<endl; visit[now]=true; int len=rev_edg[now].size(); for (int x=0;len>x;x++) { int i=rev_edg[now][x]; if (visit[i]==false) { dfs_for_stamp(i,cur_stamp); } } who_get_stamp[cur_stamp++] = now; } void dfs_for_scc(int now,int scc) { visit[now]=true; int len=edg[now].size(); for (int x=0;len>x;x++) { int i=edg[now][x]; if (visit[i]==false) { dfs_for_scc(i,scc); } } in_scc[now]=scc; } int get_scc(int n) { memset(who_get_stamp,-1,sizeof(who_get_stamp)); for (int x=0;n>=x;x++) visit[x]=false; int cur_stamp=1; for (int x=1;n>=x;x++) { if (visit[x]==false) { dfs_for_stamp(x,cur_stamp); } } for (int x=0;n>=x;x++) visit[x]=false; int scc=0; for (int x=n;x>=1;x--) { if (visit[who_get_stamp[x]]==false) { dfs_for_scc(who_get_stamp[x],scc++); } } // for (int x=1;n>=x;x++) cout<<"scc["<<x<<"] = "<<in_scc[x]<<endl; for (int x=0;scc>x;x++) { sccedg[x].clear(); rudu[x]=chudu[x]=0; } // puts("in"); // cout<<"scc="<<scc<<endl; for (int i=1;n>=i;i++) { //restore edge int len=edg[i].size(); for (int j=0;len>j;j++) { int x=edg[i][j]; if (in_scc[i]==in_scc[x]) continue; sccedg[in_scc[i]].push_back(in_scc[x]); rudu[in_scc[x]]++; chudu[in_scc[i]]++; } } int ans=0; //topological sort for (int i=0;scc>i;i++) { if (rudu[i]==0) ans++; } return ans; } int main () { int T; scanf("%d",&T); for (int qq=1;T>=qq;qq++) { int n,m; scanf("%d %d",&n,&m); for (int x=1;n>=x;x++) edg[x].clear(); for (int x=1;n>=x;x++) rev_edg[x].clear(); for (int x=0;m>x;x++) { int i,j; scanf("%d %d",&i,&j); edg[i].push_back(j); rev_edg[j].push_back(i); } printf("%d\n",get_scc(n)); } }
2016年3月15日 星期二
(codeforces) 380C. Sereja and Brackets
http://codeforces.com/contest/380/problem/C
總共花了8hr，<(_ _)>
各種case要討論啊~~~
//XXXXXYYYYZZZZ ㄌㄟ
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <assert.h>
using namespace std;
struct VAL {
int type;
int num;
void change(int b,int c) {
type=b;
num=c;
}
};
struct Val {
VAL pre;
VAL suf;
int ans;
void change_pre(int type,int num) {
pre.change(type,num);
}
void change_suf(int type,int num) {
suf.change(type,num);
}
void change_ans(int Ans) {
ans = Ans;
}
int pre_type() {
return pre.type;
}
int pre_num() {
return pre.num;
}
int suf_num() {
return suf.num;
}
int suf_type() {
return suf.type;
}
int get_ans() {
return ans;
}
};
Val empty;
bool EMPTY(Val val){
if (val.ans==2147483647) return true;
else return false;
}
Val PULL(Val a, Val b) {
if (EMPTY(a)) return b;
else if (EMPTY(b)) return a;
Val val;
int ans=a.get_ans() + b.get_ans();
int type;
int num;
if (a.suf_type() == b.pre_type()) {
if (a.pre_type() == a.suf_type() && b.pre_type()==b.suf_type()) { // >> + >> or << + << or 00+00
// puts("in-3");
assert(a.pre_num() == a.suf_num());
type=a.pre_type();
num=a.pre_num() + b.pre_num();
if (type==0) num=0;
val.change_ans(ans);
val.change_pre(type,num);
val.change_suf(type,num);
}
else if (b.pre_type()==b.suf_type()) { // >><< + << !!!
// puts("in-2");
assert(a.pre_type() == -1);
val.change_pre(a.pre_type(),a.pre_num());
val.change_ans(ans);
assert(a.suf_type() == 1);
val.change_suf(a.suf_type(),a.suf_num() + b.pre_num());
}
else if (a.pre_type()==a.suf_type()) { // > + ><
val.change_ans(ans);
val.change_pre(a.pre_type(),a.pre_num()+b.pre_num());
val.change_suf(b.suf_type(),b.suf_num());
}
}
else if (a.suf_type()==0) {
assert(a.pre_type() == 0);
val.change_ans(ans);
val.change_pre(b.pre_type(), b.pre_num());
val.change_suf(b.suf_type(), b.suf_num());
}
else if (b.pre_type()==0) {
assert(b.suf_type() == 0);
val.change_ans(ans);
val.change_pre(a.pre_type(), a.pre_num());
val.change_suf(a.suf_type(), a.suf_num());
}
else if (a.suf_type()==1) { //<< + >><< or << + >> or >><< + >> or >><< + >>><<
assert(b.pre_type()==-1);
if (b.suf_type()==1) { //case (>>)<< + >><<
if (a.suf_num() > b.pre_num()) { //(>>)<< + ><<
ans+=b.pre_num();
val.change_ans(ans);
if (a.pre_type() == 1)val.change_pre(a.pre_type(),a.suf_num() - b.pre_num() + b.suf_num());
else val.change_pre(a.pre_type(),a.pre_num());
val.change_suf(b.suf_type(),a.suf_num() - b.pre_num() + b.suf_num());
}
else if (a.suf_num() < b.pre_num()) { //(>>)<< + >>><<
ans+=a.suf_num();
val.change_ans(ans);
if (a.pre_type()==1) val.change_pre(b.pre_type(),b.pre_num() - a.suf_num());
else if(a.pre_type()==-1) val.change_pre(a.pre_type(), a.pre_num() + b.pre_num() - a.suf_num());
val.change_suf(b.suf_type(),b.suf_num());
}
else if (a.suf_num() == b.pre_num()) {
ans+=a.suf_num();
val.change_ans(ans);
if (a.pre_type()==-1) val.change_pre(a.pre_type(),a.pre_num());
else if (a.pre_type()==1) val.change_pre(b.suf_type(),b.suf_num());
val.change_suf(b.suf_type(),b.suf_num());
}
}
else if (b.suf_type() == -1) { //(>>)<< + >>
if (a.suf_num() > b.pre_num()) { //(>>)<< + >
ans+=b.pre_num();
val.change_ans(ans);
if (a.pre_type() == 1)val.change_pre(a.pre_type(),a.suf_num() - b.pre_num());
else if (a.pre_type() == -1)val.change_pre(a.pre_type(),a.pre_num());
val.change_suf(a.suf_type(),a.suf_num()-b.pre_num());
}
else if (a.suf_num() < b.pre_num()) { //(>>)<< + >>>
ans+=a.suf_num();
val.change_ans(ans);
int num=b.pre_num() - a.suf_num();
if (a.pre_type()==1) ;
else if(a.pre_type()==-1) num+=a.pre_num();
val.change_pre(b.pre_type(),num);
val.change_suf(b.suf_type(),num);
}
else if (a.suf_num() == b.pre_num()) { // >< + >
ans += a.suf_num();
val.change_ans(ans);
if (a.pre_type()==-1) val.change_pre(a.pre_type(),a.pre_num());
else if (a.pre_type()==1) val.change_pre(0,0);
if (a.pre_type()==-1) val.change_suf(a.pre_type(),a.pre_num());
else if (a.pre_type()==1) val.change_suf(0,0);
}
}
}
else if (b.suf_type() == 1) { //>>>+<<
val.change_pre(a.pre_type(),a.pre_num());
val.change_suf(b.suf_type(),b.suf_num());
val.change_ans(ans);
}
return val;
}
struct Node {
Node* lc;
Node* rc;
Val val;
Node() {
lc = rc=NULL;
val.change_pre(0,0);
val.change_suf(0,0);
val.change_ans(0);
}
void pull() {
val = PULL(lc->val,rc->val);
}
};
string s;
Node* Build(int L,int R) {
Node* node = new Node();
if (L==R) {
if (s[L]=='(') {
node->val.change_pre(1,1);
node->val.change_suf(1,1);
node->val.change_ans(0);
}
else {
node->val.change_pre(-1,1);
node->val.change_suf(-1,1);
node->val.change_ans(0);
}
return node;
}
int mid=(L+R)>>1;
node->lc=Build(L,mid);
node->rc=Build(mid+1,R);
node->pull();
// cout<<L<<"~"<<R<<" : "<<node->val.get_ans()<<endl;
// cout<<"pre_type = "<<node->val.pre_type() << " , num = "<<node->val.pre_num()<<endl;
// cout<<"suf_type = "<<node->val.suf_type() << " , num = "<<node->val.suf_num()<<endl;
return node;
}
Val query(Node* node,int L,int R,int l,int r) {
if (L>r || l>R) return empty;
else if (l<=L && R<=r) {
Val c = node->val;
// cout<<L<<"~"<<R<<" : ans = "<<c.get_ans()<<endl;
// cout<<"pre_type = "<<c.pre_type() << " , num = "<<c.pre_num()<<endl;
// cout<<"suf_type = "<<c.suf_type() << " , num = "<<c.suf_num()<<endl;
return node->val;
}
int mid=(L+R)>>1;
Val a=query(node->lc,L,mid,l,r);
Val b=query(node->rc,mid+1,R,l,r);
Val c=PULL(a,b);
// cout<<L<<"~"<<R<<" : ans = "<<c.get_ans()<<endl;
// cout<<"pre_type = "<<c.pre_type() << " , num = "<<c.pre_num()<<endl;
// cout<<"suf_type = "<<c.suf_type() << " , num = "<<c.suf_num()<<endl;
return c;
// return PULL(query(node->lc,L,mid,l,r),query(node->rc,mid+1,R,l,r));
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
string tmp;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while (cin >> tmp) {
empty.change_pre(0,0);
empty.change_suf(0,0);
empty.change_ans(2147483647);
s = " " + tmp;
int n=tmp.size();
Node* root = Build(1,n);
int m;
cin >> m;
for (int x=0;m>x;x++) {
int i,j;
cin >> i >> j;
cout << query(root,1,n,i,j).ans * 2<<endl;
}
}
}
總共花了8hr，<(_ _)>
各種case要討論啊~~~
//XXXXXYYYYZZZZ ㄌㄟ
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <assert.h>
using namespace std;
struct VAL {
int type;
int num;
void change(int b,int c) {
type=b;
num=c;
}
};
struct Val {
VAL pre;
VAL suf;
int ans;
void change_pre(int type,int num) {
pre.change(type,num);
}
void change_suf(int type,int num) {
suf.change(type,num);
}
void change_ans(int Ans) {
ans = Ans;
}
int pre_type() {
return pre.type;
}
int pre_num() {
return pre.num;
}
int suf_num() {
return suf.num;
}
int suf_type() {
return suf.type;
}
int get_ans() {
return ans;
}
};
Val empty;
bool EMPTY(Val val){
if (val.ans==2147483647) return true;
else return false;
}
Val PULL(Val a, Val b) {
if (EMPTY(a)) return b;
else if (EMPTY(b)) return a;
Val val;
int ans=a.get_ans() + b.get_ans();
int type;
int num;
if (a.suf_type() == b.pre_type()) {
if (a.pre_type() == a.suf_type() && b.pre_type()==b.suf_type()) { // >> + >> or << + << or 00+00
// puts("in-3");
assert(a.pre_num() == a.suf_num());
type=a.pre_type();
num=a.pre_num() + b.pre_num();
if (type==0) num=0;
val.change_ans(ans);
val.change_pre(type,num);
val.change_suf(type,num);
}
else if (b.pre_type()==b.suf_type()) { // >><< + << !!!
// puts("in-2");
assert(a.pre_type() == -1);
val.change_pre(a.pre_type(),a.pre_num());
val.change_ans(ans);
assert(a.suf_type() == 1);
val.change_suf(a.suf_type(),a.suf_num() + b.pre_num());
}
else if (a.pre_type()==a.suf_type()) { // > + ><
val.change_ans(ans);
val.change_pre(a.pre_type(),a.pre_num()+b.pre_num());
val.change_suf(b.suf_type(),b.suf_num());
}
}
else if (a.suf_type()==0) {
assert(a.pre_type() == 0);
val.change_ans(ans);
val.change_pre(b.pre_type(), b.pre_num());
val.change_suf(b.suf_type(), b.suf_num());
}
else if (b.pre_type()==0) {
assert(b.suf_type() == 0);
val.change_ans(ans);
val.change_pre(a.pre_type(), a.pre_num());
val.change_suf(a.suf_type(), a.suf_num());
}
else if (a.suf_type()==1) { //<< + >><< or << + >> or >><< + >> or >><< + >>><<
assert(b.pre_type()==-1);
if (b.suf_type()==1) { //case (>>)<< + >><<
if (a.suf_num() > b.pre_num()) { //(>>)<< + ><<
ans+=b.pre_num();
val.change_ans(ans);
if (a.pre_type() == 1)val.change_pre(a.pre_type(),a.suf_num() - b.pre_num() + b.suf_num());
else val.change_pre(a.pre_type(),a.pre_num());
val.change_suf(b.suf_type(),a.suf_num() - b.pre_num() + b.suf_num());
}
else if (a.suf_num() < b.pre_num()) { //(>>)<< + >>><<
ans+=a.suf_num();
val.change_ans(ans);
if (a.pre_type()==1) val.change_pre(b.pre_type(),b.pre_num() - a.suf_num());
else if(a.pre_type()==-1) val.change_pre(a.pre_type(), a.pre_num() + b.pre_num() - a.suf_num());
val.change_suf(b.suf_type(),b.suf_num());
}
else if (a.suf_num() == b.pre_num()) {
ans+=a.suf_num();
val.change_ans(ans);
if (a.pre_type()==-1) val.change_pre(a.pre_type(),a.pre_num());
else if (a.pre_type()==1) val.change_pre(b.suf_type(),b.suf_num());
val.change_suf(b.suf_type(),b.suf_num());
}
}
else if (b.suf_type() == -1) { //(>>)<< + >>
if (a.suf_num() > b.pre_num()) { //(>>)<< + >
ans+=b.pre_num();
val.change_ans(ans);
if (a.pre_type() == 1)val.change_pre(a.pre_type(),a.suf_num() - b.pre_num());
else if (a.pre_type() == -1)val.change_pre(a.pre_type(),a.pre_num());
val.change_suf(a.suf_type(),a.suf_num()-b.pre_num());
}
else if (a.suf_num() < b.pre_num()) { //(>>)<< + >>>
ans+=a.suf_num();
val.change_ans(ans);
int num=b.pre_num() - a.suf_num();
if (a.pre_type()==1) ;
else if(a.pre_type()==-1) num+=a.pre_num();
val.change_pre(b.pre_type(),num);
val.change_suf(b.suf_type(),num);
}
else if (a.suf_num() == b.pre_num()) { // >< + >
ans += a.suf_num();
val.change_ans(ans);
if (a.pre_type()==-1) val.change_pre(a.pre_type(),a.pre_num());
else if (a.pre_type()==1) val.change_pre(0,0);
if (a.pre_type()==-1) val.change_suf(a.pre_type(),a.pre_num());
else if (a.pre_type()==1) val.change_suf(0,0);
}
}
}
else if (b.suf_type() == 1) { //>>>+<<
val.change_pre(a.pre_type(),a.pre_num());
val.change_suf(b.suf_type(),b.suf_num());
val.change_ans(ans);
}
return val;
}
struct Node {
Node* lc;
Node* rc;
Val val;
Node() {
lc = rc=NULL;
val.change_pre(0,0);
val.change_suf(0,0);
val.change_ans(0);
}
void pull() {
val = PULL(lc->val,rc->val);
}
};
string s;
Node* Build(int L,int R) {
Node* node = new Node();
if (L==R) {
if (s[L]=='(') {
node->val.change_pre(1,1);
node->val.change_suf(1,1);
node->val.change_ans(0);
}
else {
node->val.change_pre(-1,1);
node->val.change_suf(-1,1);
node->val.change_ans(0);
}
return node;
}
int mid=(L+R)>>1;
node->lc=Build(L,mid);
node->rc=Build(mid+1,R);
node->pull();
// cout<<L<<"~"<<R<<" : "<<node->val.get_ans()<<endl;
// cout<<"pre_type = "<<node->val.pre_type() << " , num = "<<node->val.pre_num()<<endl;
// cout<<"suf_type = "<<node->val.suf_type() << " , num = "<<node->val.suf_num()<<endl;
return node;
}
Val query(Node* node,int L,int R,int l,int r) {
if (L>r || l>R) return empty;
else if (l<=L && R<=r) {
Val c = node->val;
// cout<<L<<"~"<<R<<" : ans = "<<c.get_ans()<<endl;
// cout<<"pre_type = "<<c.pre_type() << " , num = "<<c.pre_num()<<endl;
// cout<<"suf_type = "<<c.suf_type() << " , num = "<<c.suf_num()<<endl;
return node->val;
}
int mid=(L+R)>>1;
Val a=query(node->lc,L,mid,l,r);
Val b=query(node->rc,mid+1,R,l,r);
Val c=PULL(a,b);
// cout<<L<<"~"<<R<<" : ans = "<<c.get_ans()<<endl;
// cout<<"pre_type = "<<c.pre_type() << " , num = "<<c.pre_num()<<endl;
// cout<<"suf_type = "<<c.suf_type() << " , num = "<<c.suf_num()<<endl;
return c;
// return PULL(query(node->lc,L,mid,l,r),query(node->rc,mid+1,R,l,r));
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
string tmp;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while (cin >> tmp) {
empty.change_pre(0,0);
empty.change_suf(0,0);
empty.change_ans(2147483647);
s = " " + tmp;
int n=tmp.size();
Node* root = Build(1,n);
int m;
cin >> m;
for (int x=0;m>x;x++) {
int i,j;
cin >> i >> j;
cout << query(root,1,n,i,j).ans * 2<<endl;
}
}
}
2016年3月14日 星期一
(codeforces) 459D. Pashmak and Parmida's problem
http://codeforces.com/contest/459/problem/D
各種線段樹的應用！！！
快要瘋掉了XDDD
寫單純的copy on write還不夠，還有離散化！！！
//這題好複雜XDDD
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 1000003;
vector<int> b;
int a[MAX_N];
int dp[MAX_N];
int dp2[MAX_N];
int cnt[MAX_N];
typedef long long LL;
struct Node {
Node* lc;
Node* rc;
LL val;
Node() {
lc=rc=NULL;
val=-1;
}
};
void modify(Node* node,int L,int R,int pos,int val) {
if (L==R) {
node->val=val;
return;
}
int mid=(L+R)>>1;
if (pos<=mid) {
if (node->lc==NULL) node->lc=new Node();
modify(node->lc,L,mid,pos,val);
}
else {
if (node->rc==NULL) node->rc=new Node();
modify(node->rc,mid+1,R,pos,val);
}
}
int query(Node* node,int L,int R,int pos) {
if (pos>R || L>pos) return -1;
if (L==R) {
return node->val;
}
int mid=(L+R)>>1;
if (pos<=mid) {
if (node->lc==NULL) return -1;
else return query(node->lc,L,mid,pos);
}
else if (pos>mid) {
if (node->rc==NULL) return -1;
else return query(node->rc,mid+1,R,pos);
}
}
struct Query {
Query* lc;
Query* rc;
int val;
Query() {
lc=rc=NULL;
val=0;
}
void pull() {
val=lc->val + rc->val;
}
};
Query* Build(int L,int R) {
Query* queRy = new Query();
if (L==R) {
queRy->val = cnt[L];
return queRy;
}
int mid=(L+R)>>1;
queRy->lc=Build(L,mid);
queRy->rc=Build(mid+1,R);
queRy->pull();
return queRy;
}
void modify(Query* quEry,int L,int R,int pos,int val) {
if (L==R) {
quEry->val=val;
return;
}
int mid=(L+R)>>1;
if (pos<=mid) modify(quEry->lc,L,mid,pos,val);
else modify(quEry->rc,mid+1,R,pos,val);
quEry->pull();
}
int QUERY(Query* quEry,int L,int R,int l,int r) {
if (L>r || l>R) return 0;
else if (l<=L && R<=r) {
return quEry->val;
}
int mid=(L+R)>>1;
return QUERY(quEry->lc,L,mid,l,r)+QUERY(quEry->rc,mid+1,R,l,r);
}
const int MAX_A = 1e09 + 2;
int main () {
int n;
while (scanf("%d",&n) != EOF) {
memset(dp,0,sizeof(dp));
memset(dp2,0,sizeof(dp2));
Node* root = new Node();
for (int x=0;n>x;x++) {
scanf("%d",&a[x]);
b.push_back(a[x]);
}
sort(b.begin(),b.end());
b.resize(unique(b.begin(),b.end()) - b.begin());
for (int x=0;n>x;x++) {
a[x] = lower_bound(b.begin(),b.end(),a[x]) - b.begin();
a[x]+=1;
int val=a[x];
int pos=query(root,1,MAX_A,val);
// cout<<"pos="<<pos<<endl;
if (pos==-1) {
dp[x]=1;
modify(root,1,MAX_A,val,x);
}
else {
dp[x]=dp[pos]+1;
modify(root,1,MAX_A,val,x);
}
}
for (int x=n-1;x>=0;x--) {
int val=a[x];
int pos=query(root,1,MAX_A,val);
if (pos==-1) {
dp2[x]=1;
modify(root,1,MAX_A,val,x);
}
else {
dp2[x]=dp2[pos]+1;
modify(root,1,MAX_A,val,x);
}
}
memset(cnt,0,sizeof(cnt));
// for (int x=0;n>x;x++) cout<<dp[x]<<endl;
// for (int x=0;n>x;x++) cout <<dp2[x]<<endl;
long long ans=0;
for (int x=0;n>x;x++) cnt[dp2[x]]++;
Query* qUery = Build(1,n);
for (int x=0;n>x;x++) {
// cout<<"x="<<x<<" ; ans="<<ans<<endl;
modify(qUery,1,n,dp2[x],(--cnt[dp2[x]]));
if (dp[x]!=1)ans+= QUERY(qUery,1,n,1,dp[x]-1);
}
printf("%I64d\n",ans);
}
}
各種線段樹的應用！！！
快要瘋掉了XDDD
寫單純的copy on write還不夠，還有離散化！！！
//這題好複雜XDDD
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 1000003;
vector<int> b;
int a[MAX_N];
int dp[MAX_N];
int dp2[MAX_N];
int cnt[MAX_N];
typedef long long LL;
struct Node {
Node* lc;
Node* rc;
LL val;
Node() {
lc=rc=NULL;
val=-1;
}
};
void modify(Node* node,int L,int R,int pos,int val) {
if (L==R) {
node->val=val;
return;
}
int mid=(L+R)>>1;
if (pos<=mid) {
if (node->lc==NULL) node->lc=new Node();
modify(node->lc,L,mid,pos,val);
}
else {
if (node->rc==NULL) node->rc=new Node();
modify(node->rc,mid+1,R,pos,val);
}
}
int query(Node* node,int L,int R,int pos) {
if (pos>R || L>pos) return -1;
if (L==R) {
return node->val;
}
int mid=(L+R)>>1;
if (pos<=mid) {
if (node->lc==NULL) return -1;
else return query(node->lc,L,mid,pos);
}
else if (pos>mid) {
if (node->rc==NULL) return -1;
else return query(node->rc,mid+1,R,pos);
}
}
struct Query {
Query* lc;
Query* rc;
int val;
Query() {
lc=rc=NULL;
val=0;
}
void pull() {
val=lc->val + rc->val;
}
};
Query* Build(int L,int R) {
Query* queRy = new Query();
if (L==R) {
queRy->val = cnt[L];
return queRy;
}
int mid=(L+R)>>1;
queRy->lc=Build(L,mid);
queRy->rc=Build(mid+1,R);
queRy->pull();
return queRy;
}
void modify(Query* quEry,int L,int R,int pos,int val) {
if (L==R) {
quEry->val=val;
return;
}
int mid=(L+R)>>1;
if (pos<=mid) modify(quEry->lc,L,mid,pos,val);
else modify(quEry->rc,mid+1,R,pos,val);
quEry->pull();
}
int QUERY(Query* quEry,int L,int R,int l,int r) {
if (L>r || l>R) return 0;
else if (l<=L && R<=r) {
return quEry->val;
}
int mid=(L+R)>>1;
return QUERY(quEry->lc,L,mid,l,r)+QUERY(quEry->rc,mid+1,R,l,r);
}
const int MAX_A = 1e09 + 2;
int main () {
int n;
while (scanf("%d",&n) != EOF) {
memset(dp,0,sizeof(dp));
memset(dp2,0,sizeof(dp2));
Node* root = new Node();
for (int x=0;n>x;x++) {
scanf("%d",&a[x]);
b.push_back(a[x]);
}
sort(b.begin(),b.end());
b.resize(unique(b.begin(),b.end()) - b.begin());
for (int x=0;n>x;x++) {
a[x] = lower_bound(b.begin(),b.end(),a[x]) - b.begin();
a[x]+=1;
int val=a[x];
int pos=query(root,1,MAX_A,val);
// cout<<"pos="<<pos<<endl;
if (pos==-1) {
dp[x]=1;
modify(root,1,MAX_A,val,x);
}
else {
dp[x]=dp[pos]+1;
modify(root,1,MAX_A,val,x);
}
}
for (int x=n-1;x>=0;x--) {
int val=a[x];
int pos=query(root,1,MAX_A,val);
if (pos==-1) {
dp2[x]=1;
modify(root,1,MAX_A,val,x);
}
else {
dp2[x]=dp2[pos]+1;
modify(root,1,MAX_A,val,x);
}
}
memset(cnt,0,sizeof(cnt));
// for (int x=0;n>x;x++) cout<<dp[x]<<endl;
// for (int x=0;n>x;x++) cout <<dp2[x]<<endl;
long long ans=0;
for (int x=0;n>x;x++) cnt[dp2[x]]++;
Query* qUery = Build(1,n);
for (int x=0;n>x;x++) {
// cout<<"x="<<x<<" ; ans="<<ans<<endl;
modify(qUery,1,n,dp2[x],(--cnt[dp2[x]]));
if (dp[x]!=1)ans+= QUERY(qUery,1,n,1,dp[x]-1);
}
printf("%I64d\n",ans);
}
}
(Zj) b373: [福州19中]车厢重组 [逆序數對] [BIT]
http://zerojudge.tw/ShowProblem?problemid=b373
題目大意：求用bubble_sort需要交換的次數
其實就是逆序數對的數量(文章底部有challenge喔)
解法一：用分治法輕鬆 O(n lg n) 解決XDDD
解法二：數值線段樹
解法三：BIT
Challenge : 如果現在是問有多少數對，只得q <= ai-aj <= p 呢？
例如：http://sprout.tw/oj/pro/245/
這個時候，我們可以寫棵treap去揍他
題目大意：求用bubble_sort需要交換的次數
其實就是逆序數對的數量(文章底部有challenge喔)
解法一：用分治法輕鬆 O(n lg n) 解決XDDD
#include <iostream> #include <stdio.h> #include <algorithm> using namespace std; typedef long long ll; ll num[1000001]; ll tmp[1000001]; bool used[1000001]; ll sum; int n; void print_array(int l,int r) { for (int x=l;r>x;x++) cout << num[x] <<' '; cout <<endl; } void get_ans(int l,int r) { if (l+1==r) return; int mid=(l+r)/2; get_ans(l,mid); get_ans(mid,r); int L=l,R=mid,k=l; int times=0; long long tmpsum=0; /*cout << "In l = " << l << " ; r = " << r << endl; cout <<"Array : ";*/ //print_array(l,r); while (L < mid || R < r) { if (L==mid) tmp[k++] = num[R++]; else if (R==r) { if (used[L]!=true) sum+= num[L]*times + tmpsum; tmp[k++]=num[L++]; } else if (num[L] <= num[R]) { if (used[L] == false) sum+= num[L]*times + tmpsum; tmp[k++]=num[L++]; } else if (num[L] > num[R]) { times++; tmpsum+=num[R]; if (used[L]==false) { sum+= num[L]*times + tmpsum; used[L]=true; } else { sum += num[L]+num[R]; } tmp[k++]=num[R++]; } //cout << "Sum = " << sum << endl; sum%=10000019; } for (int x=l;r>x;x++) { num[x]=tmp[x]; used[x]=false; } } int main () { while (scanf("%d",&n) != EOF) { sum=0; for (int x=0;n>x;x++) { scanf("%d",&num[x]); } for (int x=0;1000001>x;x++) used[x]=false; get_ans(0,n); cout << sum <<endl; } }
解法二：數值線段樹
#include <iostream> #include <vector> #include <stdio.h> #include <algorithm> using namespace std; struct Node { Node* lc; Node* rc; int val; Node () { lc=rc=NULL; val=0; } void pull() { val=lc->val+rc->val; } }; const int MAX_N = 100003; int num[MAX_N]; Node* Build(int L,int R) { Node* node = new Node(); if (L==R) { node->val=0; return node; } int mid=(L+R)>>1; node->lc=Build(L,mid); node->rc=Build(mid+1,R); node->pull(); return node; } void modify(Node* node,int L,int R,int pos,int val) { if (L==R) { node->val+=val; return; } int mid=(L+R)>>1; if (pos<=mid) modify(node->lc,L,mid,pos,val); else modify(node->rc,mid+1,R,pos,val); node->pull(); return; } int query(Node* node,int L,int R,int l,int r) { if (l>R || L>r )return 0; else if (l<=L && R<=r) return node->val; int mid=(L+R)>>1; return query(node->lc,L,mid,l,r) + query(node->rc,mid+1,R,l,r); } int main () { int n; while (scanf("%d",&n) != EOF) { vector<int> v; for (int x=0;n>x;x++) { scanf("%d",&num[x]); v.push_back(num[x]); } sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end()) - v.begin()); int len=v.size(); for (int x=0;n>x;x++) { // cout<<"x="<<x<<endl; num[x]=lower_bound(v.begin(),v.end(),num[x]) - v.begin(); } Node* root=Build(0,len); int ans=0; for (int x=0;n>x;x++) { // cout<<"num["<<x<<"] = "<<num[x]<<endl; if (num[x]==len-1) { modify(root,0,len,num[x],1); } else { ans+=query(root,0,len,num[x]+1,len); modify(root,0,len,num[x],1); } } printf("%d\n",ans); } }
解法三：BIT
#include <iostream> #include <stdio.h> #include <vector> #include <algorithm> using namespace std; struct BIT { vector<int> data; int n; void init(int _n) { n=_n; data.resize(n+1); fill(data.begin(),data.end(),0); } void update(int id,int val) { for(int i=id;n>=i; i += i&(-i)) { data[i] += val; } } int query(int id) { int ret=0; for (int i=id;i>0; i-=i&(-i)) { ret += data[i]; } return ret; } } bit; const int MAX_N = 10006; int a[MAX_N]; int main () { int n; while (scanf("%d",&n) != EOF) { bit.init(n); int ans=0; for (int i=1;n>=i;i++) { scanf("%d",&a[i]); ans += (bit.query(n) - bit.query(a[i])); bit.update(a[i],1); } printf("%d\n",ans); } }
Challenge : 如果現在是問有多少數對，只得q <= ai-aj <= p 呢？
例如：http://sprout.tw/oj/pro/245/
這個時候，我們可以寫棵treap去揍他
#include <iostream> #include <stdio.h> #include <ctime> #include <cstdlib> using namespace std; struct Treap { Treap* lc; Treap* rc; int key,pri,size; Treap(int _key) { lc=rc=NULL; key=_key; pri=rand(); size=1; } }; int Size(Treap* t) { return t ? t->size : 0; } void pull(Treap* t) { t->size = 1 + Size(t->lc) + Size(t->rc); } Treap* merge(Treap* a,Treap* b) { if (!a||!b) return a?a:b; else if (a->pri > b->pri) { a->rc=merge(a->rc,b); pull(a); return a; } else { b->lc=merge(a,b->lc); pull(b); return b; } } void split(Treap* t,int k,Treap* &a,Treap* &b) { if (!t) a=b=NULL; else if (t->key <= k) { a=t; split(t->rc,k,a->rc,b); pull(a); } else { b=t; split(t->lc,k,a,b->lc); pull(b); } } //p<=aj-ai<=q //-q+aj<=ai<=-p+aj int query(Treap* root,int val,int p,int q) { Treap* tl; Treap* tr; // cout<<-q+val-1<<" ~ "<<-p+val <<endl; split(root,-q+val-1,tl,root); split(root,-p+val,root,tr); if (root!=NULL) { // cout<<"root->key = "<<root->key<<endl; pull(root); } else { // cout<<"empty\n"; } int ret=Size(root); root=merge(merge(tl,root),tr); return ret; } void dfs(Treap* t) { cout<<t->key<<' '; if (t->lc) dfs(t->lc); if (t->rc) dfs(t->rc); } int main () { srand(time(NULL)); int T; scanf("%d",&T); while (T--) { int n,p,q; scanf("%d %d %d",&n,&p,&q); long long ans=0; Treap* root=NULL; for (int x=0;n>x;x++) { // cout<<"x="<<x<<endl; int i; scanf("%d",&i); ans+=query(root,i,p,q); //root=merge(root,new Treap(i)); ==> 錯的 Treap* tl; Treap* tr; split(root,i-1,tl,root); split(root,i,root,tr); root=merge(root,new Treap(i)); root=merge(merge(tl,root),tr); } printf("%lld\n",ans); } }
2016年3月12日 星期六
USACO 2013 November Contest, Silver Problem 2. Crowded Cows (Copy on Write 線段樹模板)
http://www.usaco.org/index.php?page=viewproblem2&cpid=344
要用copy on write 線段樹支援！！！
要用copy on write 線段樹支援！！！
#include <iostream> #include <stdio.h> #include <algorithm> #include <assert.h> using namespace std; struct Node { Node* lc; Node* rc; int val; Node() { lc=rc=NULL; val=-1; } void pull() { if (lc==NULL && rc==NULL) val=-1; else if (lc==NULL && rc!=NULL) val=rc->val; else if (lc!=NULL && rc==NULL) val=lc->val; else if (lc!=NULL && rc!=NULL) val=max(rc->val,lc->val); } }; void modify(Node* node,int L,int R,int pos,int val) { //similar to build if (L==R) { assert(L==pos); node->val=val; return; } int mid=(L+R)>>1; if (pos<=mid) { if (node->lc==NULL) { Node* tmp = new Node(); node->lc=tmp; } modify(node->lc,L,mid,pos,val); } else if (pos>mid) { if (node->rc==NULL) { Node* tmp = new Node(); node->rc=tmp; } modify(node->rc,mid+1,R,pos,val); } node->pull(); } int query(Node* node,int L,int R,int l,int r) { if (L>r||l>R) return -1; else if (l<=L && R<=r) return node->val; // else if (L==R) return node->val; int mid=(L+R)>>1; int q1=-1; if (node->lc==NULL) q1=-1; else q1=query(node->lc,L,mid,l,r); int q2=-1; if (node->rc==NULL) q2=-1; else q2=query(node->rc,mid+1,R,l,r); // cout<<"return "<<max(q1,q2)<<endl; return max(q1,q2); } const int MAX_N = 50002; const int MAX_H = 1000000005; int x[MAX_N], h[MAX_N]; int main () { freopen("crowded.in","r",stdin); freopen("crowded.out","w",stdout); int n,d; while (scanf("%d %d",&n,&d) != EOF) { Node* root = new Node(); for (int i=0;n>i;i++) { scanf("%d %d",&x[i],&h[i]); modify(root,1,MAX_H,x[i],h[i]); } int ans=0; //start query for (int i=0;n>i;i++) { //left side int anss=0; if (x[i]!=1) { int L=(x[i]-d),R=x[i]-1; if (L<=1) L=1; int tmp=query(root,1,MAX_H,L,R); if (tmp>=2*h[i]) { anss++; } } if (x[i]!=MAX_H) { int L=(x[i]+1),R=x[i]+d; if (R>=MAX_H) R=MAX_H; int tmp=query(root,1,MAX_H,L,R); if (tmp>=2*h[i]) { anss++; } } if (anss==2) ans++; } printf("%d\n",ans); // for (int x=1;20>=x;x++) cout << x << " = " << query(root,1,MAX_H,x,20)<<endl; } }
(Zj) 區間連續最大和
http://zerojudge.tw/ShowProblem?problemid=a164
有夠難寫！！！
因為這題還要維護答案的範圍，要不然基本上，答案範圍的可以不用存XDDD
就是呢，對於每個區間，你都要維護4樣東西："最大前綴和"、"最大後綴和"、"最大區間總和"、"區間總和"，我分別以lmax, rmax, midmax, sum表示
其中，在合併時：
1. lmax = max(lc->lmax, lc->sum + rc->lmax)
2. rmax = max(rc->rmax, lc->rmax + rc->sum)
3. midmax = max( max(lc->midmax, rc->midmax) , lc->rmax + rc->lmax);
4. sum = lc->sum + rc->sum;
想想看為什麼！
然後，在求答案時：
要維護兩種答案f0(不可以連續到下一個區間), f1(可以連續到下一個區間)
維護方法分別是：
f0 = max( node->midmax , pref1 + node->lmax);
f1 = max( node->rmax, pref1+node->sum);
pref1代表上一個f1
因此，在initialize詢問時，要預設f0 = f1 = 0 !!!
太神奇啦！！！
2016.10.19 Update : 其實如果可以用treap做的話，會更直觀一點(切來切去之後，求midmax即為答案，這裡 是指標版)
這樣就AC了
有夠難寫！！！
因為這題還要維護答案的範圍，要不然基本上，答案範圍的可以不用存XDDD
就是呢，對於每個區間，你都要維護4樣東西："最大前綴和"、"最大後綴和"、"最大區間總和"、"區間總和"，我分別以lmax, rmax, midmax, sum表示
其中，在合併時：
1. lmax = max(lc->lmax, lc->sum + rc->lmax)
2. rmax = max(rc->rmax, lc->rmax + rc->sum)
3. midmax = max( max(lc->midmax, rc->midmax) , lc->rmax + rc->lmax);
4. sum = lc->sum + rc->sum;
想想看為什麼！
然後，在求答案時：
要維護兩種答案f0(不可以連續到下一個區間), f1(可以連續到下一個區間)
維護方法分別是：
f0 = max( node->midmax , pref1 + node->lmax);
f1 = max( node->rmax, pref1+node->sum);
pref1代表上一個f1
因此，在initialize詢問時，要預設f0 = f1 = 0 !!!
太神奇啦！！！
2016.10.19 Update : 其實如果可以用treap做的話，會更直觀一點(切來切去之後，求midmax即為答案，這裡 是指標版)
這樣就AC了
#include <iostream> #include <stdio.h> #include <algorithm> #include <vector> #include <math.h> typedef long long LL; const int INF = 2000000000; inline long long max(int a,int b) { return (a<b?b:a); } struct Node { Node* lc; Node* rc; int l,r,mid; int lst,led; int rst,red; int mst,med; LL lmax,rmax,midmax,sum; Node () { lc=rc=NULL; l=r=mid=lst=led=mst=med=lmax=rmax=midmax=sum=0; } void init(int pos,int val) { l=r=mid=lst=led=rst=red=mst=med=pos; lmax=rmax=midmax=sum=val; } void pull() { l=lc->l; r=rc->r; mid=(l+r)>>1; sum=lc->sum+rc->sum; lmax = max(lc->lmax, lc->sum + rc->lmax); lst=led=mst=med=rst=red=INF; if (lmax == lc->lmax) { lst=lc->lst; led=lc->led; } //其實後面可以不用，但是因為要輸出範圍XDDD if (lmax == lc->sum + rc->lmax && (lst > lc->lst || lst==lc->lst && led>rc->led)) { lst=lc->lst; //can also be = lc->l led=rc->led; } rmax = max(rc->rmax,rc->sum + lc->rmax); if (rmax == rc->rmax) { rst=rc->rst; red=rc->red; } if (rmax== rc->sum + lc->rmax && (rst > lc->rst || rst==lc->rst && led > rc->red)) { red=rc->red; //can also be = rc->r rst=lc->rst; } midmax = max(max(lc->midmax,rc->midmax) , lc->rmax + rc->lmax); if (midmax==lc->midmax) { mst=lc->mst; med=lc->med; } if (midmax==rc->midmax && (mst>rc->mst || mst==rc->mst && med>rc->med)) { mst=rc->mst; med=rc->med; } if (midmax==lc->rmax + rc->lmax && (mst>lc->rst || mst==lc->rst && med>rc->led)) { mst=lc->rst; med=rc->led; } } }; const int MAX_N = 200004; int v[MAX_N]; Node* Build(int L,int R) { Node* node = new Node(); if (L==R) { node->init(L,v[L]); return node; } int mid=(L+R)>>1; node->lc=Build(L,mid); node->rc=Build(mid+1,R); node->pull(); return node; } LL ans; int ansst,ansed; LL f0,f1; int f0st,f0ed,f1st,f1ed; void query(Node* node,int L,int R,int l,int r) { if (L>r || l>R) return; else if (l<=L && R<=r) { f0 = max(node->midmax,f1+node->lmax); if (f0==node->midmax && f0!=f1+node->lmax) { f0st=node->mst; f0ed=node->med; } else if (f0==f1+node->lmax && f0 != node->midmax) { f0st=f1st; f0ed=node->led; } else { if (node->mst < f1st || node->mst==f1st && node->med < node->led) { f0st=node->mst; f0ed=node->med; } else { f0st=f1st; f0ed=node->led; } } LL pref1=f1; f1 = max(node->rmax, pref1 + node->sum); if (f1==node->rmax && f1!=pref1+node->sum) { f1st=node->rst; f1ed=node->red; } else if (f1==pref1+node->sum && f1!=node->rmax) { f1st=f1st; f1ed=node->r; } else { if (node->rst < f1st || node->rst==f1st && node->red < node->r) { f1st=node->rst; f1ed=node->red; } else { f1st=f1st; f1ed=node->r; } } if (f0>ans || f0==ans && f0st<ansst || f0==ans&&f0st==ansst&&f0ed<ansed) { ans=f0; ansst=f0st; ansed=f0ed; } if (f1>ans || f1==ans && f1st<ansst || f1==ans&&f1st==ansst&&f1ed<ansed) { ans=f1; ansst=f1st; ansed=f1ed; } return; } int mid=(L+R)>>1; query(node->lc,L,mid,l,r); query(node->rc,mid+1,R,l,r); } int main () { int n,q,cases=0; while (scanf("%d %d",&n,&q) != EOF) { printf("Case %d:\n",++cases); for (int x=1;n>=x;x++) { scanf("%d",&v[x]); } Node* root = Build(1,n); while (q--) { int i,j; scanf("%d %d",&i,&j); ans=-INF; ansst=ansed=INF; f0 = f1 = 0; f0st = f0ed = f1st = f1ed = i; query(root,1,n,i,j); printf("%d %d %lld\n",ansst,ansed,ans); } } } /* 1. k.lmax = max(lc.lmax, lc.sum + rc.lmax); 2. k.rmax = max(rc.rmax, rc.sum + lc.rmax); 3. k.midmax = max(lc.midmax, rc.midmax, lc.rmax + rc.lmax); 4. k.sum = lc.sum + rc.sum; 接下來，當我們調查[i,j] 時，會拆成很多個不相交的區間 [i, i1] [i2, i3] [i4..] ... 目前不連續到下一個區間的最大連續和 f0 = max(k.midmax, f1 + k.lmax);區間中斷 or 連續+斷 目前可連續到下一個區間的最大連續和 f1 = max(k.rmax, f1 + k.sum);新的連續 or 連續+連續 */
訂閱：
文章 (Atom)