用了1mol多时间+借鉴(chao)了1mol多题解后终于差不多a完了(话说直接把题目copy过来让我们做真的好?)
A 线段树模板 不用多说了吧
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define sdrwr 1
using namespace std;
long long n,m,t,a,b;
long long sum[400005];
void pushup(long long rt)
{
sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}
void update(long long rt,long long l,long long r,long long q,long long x)
{
if (l==r)
{
sum[rt]=sum[rt]+x;
return;
}
long long mid=(l+r)>>1;
if (q<=mid)update(lson,q,x);
else update(rson,q,x);
pushup(rt);
}
long long query(long long rt,long long l,long long r,long long x,long long y)
{
if (l>=x&&r<=y)
{
return sum[rt];
}
long long mid=(l+r)>>1;
long long ans=0;
if (x<=mid)ans=max(ans,query(lson,x,y));
if (y>mid)ans=max(ans,query(rson,x,y));
return ans;
}
int main()
{
scanf("%lld%lld",&n,&m);
for (long long i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&t,&a,&b);
if (t==1) {update(1,1,n,a,b);}
if (t==2) {printf("%lld\n",query(1,1,n,a,b));}
}
return 0;
}
B 卿学姐与基本法
离散化的线段树,但我在网上看到了一种神奇的算法
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
map <int,int> q;
map <int,int> ::iterator w;
int t,l,r,x,y,haha;
int query(int x,int y)
{
int l=x,r=y,ans=y-x+1;
for (w=q.begin();w!=q.end();w++)
{
int a=w->first,b=w->second;
if (a>r) return ans;
else if (b<l) continue;
else if (a<l&&b>r)
{
return ans-=r-l+1;
}
else
{
if(a<=l && b<=r)
ans-=b-l+1,l=b+1;
else if(a>l && b<=r)
ans-=b-a+1,l=b+1;
else
return ans-=r-a+1;
}
}
return ans;
}
int main()
{
int n,t;
scanf("%d%d",&n,&t);
for (int i=1;i<=t;i++)
{
scanf("%d%d%d",&x,&l,&r);
if (x==1)
{
if(q[l]<r) q[l]=r;
}
else printf("%d\n",query(l,r));
}
}C 卿学姐与诡异村庄
并查集,开两倍内存,如果是一个人另外一个人说是好人,就说明是同类,反之不是.所以如果是一就find(x,y);和find(x+n,y+n);否则find(x,y+n)和find(x+n,y);如果有矛盾就懵逼,否则就行.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
int fa[200005],x,t,n,sdf;
int find(int x)
{
if (fa[x]==x) return fa[x];
else return fa[x]=find(fa[x]);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=2*n;i++)
fa[i]=i;
for (int i=1;i<=n;i++)
{
scanf("%d%d",&x,&t);
if (t==1)
{
int x2=find(x);
int y2=find(i);
if (x2!=y2)
{
fa[x2]=y2;
}
x2=find(x+n);
y2=find(i+n);
if (x2!=y2)
{
fa[x2]=y2;
}
}
else
{
int x2=find(x+n);
int y2=find(i);
if (x2!=y2)
{
fa[x2]=y2;
}
x2=find(x);
y2=find(i+n);
if (x2!=y2)
{
fa[x2]=y2;
}
}
}
for (int i=1;i<=n;i++)
{
if (find(i)==find(i+n))
{
printf("One face meng bi");
return 0;
}
}
printf("Time to show my power");
return 0;
}D 卿学姐与魔法
优先队列,排序,再把所有(a[i]+b[1],1)压进去就Ok,弹出时把b的下一个压进去即可,水题一枚
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
int n,a[100005],b[100005],d[100005],ans,cnt=1,min1,min2;
typedef pair<int,int >pii;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
for (int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
}
sort(b+1,b+1+n);
priority_queue<pii, vector<pii>, greater<pii> > q;
for (int i=1;i<=n;i++)
{
q.push(make_pair(a[i]+b[1],1));
}
int t=1;
for (int i=1;i<=n;i++)
{
pii u=q.top();
q.pop();
q.push(make_pair(u.first-b[u.second]+b[u.second+1],u.second+1));
printf("%d\n",u.first);
}
return 0;
}E 卿学姐与城堡的墙
离散化树状数组,蛤蛤蛤,
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define ll long long
#define maxn 200005
struct Line
{
ll y1, y2;
bool operator < (Line x)const
{
return y1 < x.y1;
}
}line[maxn];
int N;
ll u, v, data[maxn];
ll tree[maxn];
void update(int i, ll val)
{
while (i <= N)
{
tree[i] += val;
i += i&(-i);
}
}
ll query(int i)
{
ll sum = 0;
while (i)
{
sum += tree[i];
i -= i&(-i);
}
return sum;
}
int main()
{
scanf("%d%lld%lld", &N, &u, &v);
ll a, b;
for (int i = 0; i < N; ++i)
{
scanf("%lld%lld", &a, &b);
line[i].y1 = a*u + b, line[i].y2 = a*v + b;
data[i] = line[i].y2;
}
sort(line, line + N);
sort(data, data + N);
int num = unique(data, data + N) - data;
for (int i = 0; i < N; ++i)
line[i].y2 = lower_bound(data, data + num, line[i].y2) - data + 1;
ll ans = 0;
int last = 0;
for (int i = 0; i < N; ++i)
{
if (i > 0 && line[i].y1 == line[i - 1].y1)
{
//++ans;
ans += i - last;
}
else
{
ans += i - query(line[i].y2 - 1);
last = i;
}
update(line[i].y2, 1);
}
printf("%lld\n", ans);
return 0;
}