数据结构以及图论补充-创新互联
线段树：
一、单点修改，区间查询
#pragma GCC optimize(3,"Ofast","inline")
#includeusing namespace std;
typedef long long ll;
const int maxn = 2e5 + 100;
int n, Q;
int a[maxn];
int suma[maxn];
typedef struct
{int l, r;
int sum;
}T;
T t[maxn<< 1];
inline void build(int rt, int l, int r)
{t[rt].l = l;
t[rt].r = r;
if (l == r)
{t[rt].sum = a[l];
return;
}
int mid = (l + r) >>1;
build(rt<< 1, l, mid);
build(rt<< 1 | 1, mid + 1, r);
t[rt].sum = t[rt<< 1].sum + t[rt<< 1 | 1].sum;
}
inline int interval_add(int rt, int l, int r)
{if (t[rt].l >= l && t[rt].r<= r)return t[rt].sum;
if (t[rt].l >r || t[rt].r< l)return 0;
int temp = 0;
if (t[rt<< 1].r >= l)temp += interval_add(rt<< 1, l, r);
if (t[rt<< 1 | 1].l<= r)temp += interval_add(rt<< 1 | 1, l, r);
return temp;
}
inline void point_modify(int rt, int pos, int val)
{if (t[rt].l == t[rt].r)
{t[rt].sum += val;
return;
}
if (pos<= t[rt<< 1].r)point_modify(rt<< 1, pos, val);
else point_modify(rt<< 1 | 1, pos, val);
t[rt].sum = t[rt<< 1].sum + t[rt<< 1 | 1].sum;
return;
}
int main()
{ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >>n;
for (int i = 1; i<= n; i++)cin >>a[i], suma[i] = suma[i - 1] + a[i];
build(1, 1, n);
cin >>Q;
while (Q--)
{bool f;
cin >>f;
if (f)
{ int l, r;
cin >>l >>r;
cout<< interval_add(1, l, r)<< "\n";
}
else
{ int p, v;
cin >>p >>v;
point_modify(1, p, v);
a[p] += v;
for (int i = 1; i<= n; i++)cout<< a[i]<< " ";
cout<< "\n";
}
}
} 二.区间修改，单点查询
#pragma GCC optimize(3,"Ofast","inline")
#includeusing namespace std;
typedef long long ll;
const int maxn = 2e5 + 100;
int n, Q;
int a[maxn];
int suma[maxn];
typedef struct
{int l, r;
int sum;
}T;
T t[maxn<< 1];
inline void build(int rt, int l, int r)
{t[rt].l = l;
t[rt].r = r;
if (l == r)
{t[rt].sum = a[l];
return;
}
int mid = (l + r) >>1;
build(rt<< 1, l, mid);
build(rt<< 1 | 1, mid + 1, r);
}
inline void interval_modify(int rt, int l, int r, int val)
{if (t[rt].l >= l && t[rt].r<= r)
{t[rt].sum += val;
return;
}
int mid = t[rt].l + t[rt].r >>1;
if (l<= mid)interval_modify(rt<< 1, l, r, val);
if (r >mid)interval_modify(rt<< 1 | 1, l, r, val);
}
inline int point_ask(int rt, int pos)
{int ans = 0;
ans += t[rt].sum;
if (t[rt].l == t[rt].r)return ans;
int mid = t[rt].l + t[rt].r >>1;
if (pos<= mid) ans += point_ask(rt<< 1, pos);
if (pos >mid)ans += point_ask(rt<< 1 | 1, pos);
return ans;
}
int main()
{ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >>n; cin >>Q;
for (int i = 1; i<= n; i++)cin >>a[i], suma[i] = suma[i - 1] + a[i];
build(1, 1, n);
while (Q--)
{bool f;
cin >>f;
if (f)
{ int l, r, v;
cin >>l >>r >>v;
interval_modify(1, l, r, v);
for (int i = l; i<= r; i++)a[i] += v;
for (int i = 1; i<= n; i++)cout<< a[i]<< " ";
cout<< "\n";
}
else
{ int pos;
cin >>pos;
cout<< point_ask(1, pos)<< "\n";
}
}
return 0;
} 扫描线法
#pragma GCC optimize(3,"Ofast","inline")
#includeusing namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;
typedef struct line
{double x, y1, y2;
int c;
bool friend operator<(line p, line q)
{return p.x< q.x;
}
}A;
A a[maxn<< 1];
typedef struct tree
{int l, r;
int cnt;
double len;
}T;
T t[maxn<< 2];
int n;
double raw[maxn<< 1];
int cnt;
double ans;
int val[maxn<< 1][2];
inline void build(int rt, int l, int r)
{t[rt].l = l;
t[rt].r = r;
t[rt].cnt = 0;
t[rt].len = 0;
if (l == r)return;
int mid = l + r >>1;
build(rt<< 1, l, mid);
build(rt<< 1 | 1, mid + 1, r);
}
void push_up(int rt)
{if (t[rt].cnt >0)t[rt].len = raw[t[rt].r + 1] - raw[t[rt].l];
else if (t[rt].l == t[rt].r)t[rt].len = 0;
else t[rt].len = t[rt<< 1].len + t[rt<< 1 | 1].len;
}
void interval_modify(int rt, int l, int r, int val)
{if (t[rt].l >= l && t[rt].r<= r)
{t[rt].cnt += val;
push_up(rt);
return;
}
int mid = t[rt].l + t[rt].r >>1;
if (l<= mid)interval_modify(rt<< 1, l, r, val);
if (r >mid)interval_modify(rt<< 1 | 1, l, r, val);
push_up(rt);
}
int main()
{ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int casenum = 0;
while (cin >>n && n)
{cnt = 0;
ans = 0;
for (int i = 1; i<= n; i++)
{ double x1, y1, x2, y2;
cin >>x1 >>y1 >>x2 >>y2;
a[i * 2 - 1] = {x1,y1,y2,1 };
a[i * 2] = {x2,y1,y2,-1 };
raw[++cnt] = y1;
raw[++cnt] = y2;
}
sort(a + 1, a + 1 + 2 * n);
sort(raw + 1, raw + 1 + cnt);
cnt = unique(raw + 1, raw + 1 + cnt) - (raw + 1);
for (int i = 1; i<= n * 2; i++)
{ val[i][0] = lower_bound(raw + 1, raw + 1 + cnt, a[i].y1) - raw;
val[i][1] = lower_bound(raw + 1, raw + 1 + cnt, a[i].y2) - raw;
}
build(1, 1, cnt);
for (int i = 1; i<= 2 * n; i++)
{ interval_modify(1, val[i][0], val[i][1] - 1, a[i].c);
ans += (a[i + 1].x - a[i].x) * t[1].len;
}
cout<< "Test case #"<< ++casenum<< "\n";
cout<< "Total explored area: "<< fixed<< setprecision(2)<< ans<< "\n";
cout<< "\n";
}
return 0;
} 单点修改，区间查询大子段和
#pragma GCC optimize(3,"Ofast","inline")
#includeusing namespace std;
typedef long long ll;
const int maxn = 5e5 + 100;
int n, Q;
int a[maxn];
int suma[maxn];
typedef struct node
{int l, r;
int sum;
int dat;
int lmax, rmax;
node()
{l = r = sum = dat = lmax = rmax = 0;
}
}T;
T t[maxn<< 2];
inline void build(int rt, int l, int r)
{t[rt].l = l;
t[rt].r = r;
if (l == r)
{t[rt].sum = a[l];
t[rt].lmax = t[rt].rmax = t[rt].dat = a[l];
return;
}
int mid = (l + r) >>1;
build(rt<< 1, l, mid);
build(rt<< 1 | 1, mid + 1, r);
t[rt].sum = t[rt<< 1].sum + t[rt<< 1 | 1].sum;
t[rt].lmax = max(t[rt<< 1].lmax, t[rt<< 1].sum + t[rt<< 1 | 1].lmax);
t[rt].rmax = max(t[rt<< 1 | 1].rmax, t[rt<< 1].rmax + t[rt<< 1 | 1].sum);
t[rt].dat = max(t[rt<< 1].dat, t[rt<< 1 | 1].dat);
t[rt].dat = max(t[rt].dat, t[rt<< 1].rmax + t[rt<< 1 | 1].lmax);
}
inline void point_modify(int rt, int pos, int val)
{if (t[rt].l == t[rt].r)
{t[rt].sum = t[rt].dat = t[rt].lmax = t[rt].rmax = val;
return;
}
int mid = t[rt].l + t[rt].r >>1;
if (pos<= mid)point_modify(rt<< 1, pos, val);
else point_modify(rt<< 1 | 1, pos, val);
t[rt].sum = t[rt<< 1].sum + t[rt<< 1 | 1].sum;
t[rt].lmax = max(t[rt<< 1].lmax, t[rt<< 1].sum + t[rt<< 1 | 1].lmax);
t[rt].rmax = max(t[rt<< 1 | 1].rmax, t[rt<< 1].rmax + t[rt<< 1 | 1].sum);
t[rt].dat = max(t[rt<< 1].dat, t[rt<< 1 | 1].dat);
t[rt].dat = max(t[rt].dat, t[rt<< 1].rmax + t[rt<< 1 | 1].lmax);
return;
}
T interval_ask(int rt, int l, int r)
{ //此时的ask函数返回的是临时开的T，想一想为什么，如果是void类型ask，每次ask一个区间（l,r）dat，lmax,rmax都会随着l,r不同而修改，一定会影响后续ask
if (t[rt].l >= l && t[rt].r<= r)return t[rt];
int mid = t[rt].l + t[rt].r >>1;
if (l<= mid && r >mid)
{T tt, tl, tr;
tl = interval_ask(rt<< 1, l, r);
tr = interval_ask(rt<< 1 | 1, l, r);
tt.sum = tl.sum + tr.sum;
tt.lmax = max(tl.lmax, tl.sum + tr.lmax);
tt.rmax = max(tr.rmax, tl.rmax + tr.sum);
tt.dat = max(tl.dat, tr.dat);
tt.dat = max(tt.dat, tl.rmax + tr.lmax);
return tt;
}
else if (l<= mid)
{return interval_ask(rt<< 1, l, r);
}
else if (r >mid)
{return interval_ask(rt<< 1 | 1, l, r);
}
}
int main()
{ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >>n >>Q;
for (int i = 1; i<= n; i++)cin >>a[i];
build(1, 1, n);
while (Q--)
{int k, x, y;
cin >>k >>x >>y;
if (k & 1)
{ if (x >y)swap(x, y);
T ans = interval_ask(1, x, y);
cout<< ans.dat<< "\n";
}
else
{ point_modify(1, x, y);
}
}
return 0;
} 图论补充：第K短路（A*）
//Made In Heaven
#pragma GCC optimize(3, "Ofast", "inline")
#includeusing namespace std;
typedef long long ll;
const int maxn = 1e4 + 1000;
int n, m;
int S, E, K, T;
int dis[maxn];
int h1[maxn], h2[maxn];
bool vis1[maxn];
int num1, num2;
typedef struct
{int nt, to, w;
}EDGE;
EDGE e1[maxn], e2[maxn];
void add1(int u, int v, int w)
{e1[++num1].w = w;
e1[num1].to = v;
e1[num1].nt = h1[u];
h1[u] = num1;
}
void add2(int v, int u, int w)
{e2[++num2].w = w;
e2[num2].to = v;
e2[num2].nt = h2[u];
h2[u] = num2;
}
typedef pairP;
//反向建边dj T->S
void dj()
{memset(dis, 0x3f, sizeof(dis));
dis[E] = 0;
priority_queue, greater>q;
q.push(make_pair(dis[E], E));
while (!q.empty())
{P p = q.top();
q.pop();
int u = p.second;
int diss = p.first;
if (vis1[u])continue;
vis1[u] = 1;
for (int i = h2[u]; i; i = e2[i].nt)
{int v = e2[i].to;
if (dis[v] >diss + e2[i].w)
{dis[v] = diss + e2[i].w;
q.push(make_pair(dis[v], v));
}
}
}
}
typedef pairPP;
int A_start()
{if (dis[S] >= 0x3f3f3f3f)return -1;
priority_queue, greater>q;
q.push(make_pair(dis[S], make_pair(0, S)));
int cnt = 0;
while (!q.empty())
{PP p = q.top();
q.pop();
int u = p.second.second;
int diss = p.second.first;
if (u == E)cnt++;
if (cnt == K)return diss;
for (int i = h1[u]; i; i = e1[i].nt)
{int v = e1[i].to;
q.push(make_pair(diss + e1[i].w + dis[v], make_pair(diss + e1[i].w, v)));
}
}
return -1;
}
void init() {num1 = num2 = 0;
memset(vis1, 0, sizeof vis1);
memset(h1, 0, sizeof h1);
memset(h2, 0, sizeof h2);
}
signed main()
{ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while (cin >>n >>m) {init();
cin >>S >>E >>K >>T;
if (S == E)K++;
while (m--)
{int u, v, w;
cin >>u >>v >>w;
add1(u, v, w);
add2(u, v, w);
}
dj();
int ans = A_start();
if (ans == -1 || ans >T)cout<< "Whitesnake!\n";
else cout<< "yareyaredawa\n";
}
return 0;
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章标题：数据结构以及图论补充-创新互联
URL链接：http://scjbc.cn/article/jgcgh.html
