实际上简单的题目并不能被题目所吓到，仔细分析实际上难度并不是很高。
如果存在显然的部分分数，其实特盘一下也比较好，有可能你的程序就卡在这个地方。。
这次暴力打的不是很挂，\(T1\) 也还是差一个 \(nth\)_\(element\) ，二分答案的思路显然，但是要有两个 \(log_2\)
\(T2\) 没有进行仔细的分析，实际上手动推导发现可以推导成为一个形式，并且与深度的奇偶性有关。
\(T3\) 这个属实大神题，需要使用常熟优秀的树状数组。
Merchant
我们首先进行二分答案，二分时间，然后进行统计 \(check\)，但是发现如果在 \(check\)中使用 \(sort\),就会 \(TLE\) 成 \(78pts\) ，因为这时的复杂度是 \(nlog^2\) 。
然后我们其实可以发现，我们并不需要让他有序，我们只需要将前 \(m\) 大小的提到一边。
这时 \(nth_element\) 的作用就体现出来了，之后我们就可以 \(\mathcal O(n)\) 排除顺序，之后加和比较。
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)
namespace xin_io
{
#define debug cout<<"debug"<<endl
#define enum(x) cout<<#x" = "<<x<<endl;
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &x)
{
register type s = 0; register int f = 1; register char ch = gc();
while(!isdigit(ch)) {if(ch == ‘-‘) f = -1; ch = gc();}
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return x = s * f,*this;
}}io;
}
#define int long long
using namespace xin_io; static const int maxn = 2e6+10,inf = 1e9+7,mod = 998244353; const ll llinf = 1e18+7;
namespace xin
{
class xin_data
{
public:
int k,b;
xin_data(){}
xin_data(int k,int b):k(k),b(b){}
inline int val(int t) {return k * t + b;}
}d[maxn];
int n,m,s,temp;
int a[maxn];
inline bool comp(int x,int y) {return x > y;}
inline bool check(int x)
{
try(i,1,n) a[i] = d[i].val(x);
std::nth_element(a+1,a+(n-m),a+n+1);
s = temp;
throw(i,n,n-m+1)
{
if(a[i] < 0) continue;
s -= a[i];
if(s <= 0) return true;
}
return false;
}
inline short main()
{
io >> n >> m >> s; temp = s;
try(i,1,n) io >> d[i].k >> d[i].b;
register int l = 0,r = inf,mid;
if(check(0)) {cout<<0<<endl; return 0;}
while(l != r - 1 and l < r)
{
mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid;
}
if(check(l)) cout<<l<<endl;
else if(check(mid)) cout<<mid<<endl;
else cout<<r<<endl;
// cout<<sizeof(a) / (1 << 20)<<" MB"<<endl;
return 0;
}
}
signed main() {return xin::main();}
Equation
我们进行推导，发现每一个式子都可以推成
\[x_1=k+x_u
\]
或者
\[x_1=k-x_u
\]
这个符号取决与深度的奇偶性。
然后我们强制使树的边权正负交错，也就是 \(sum_y=w_y-sum_x\)
然后对于 \(2\) 操作，在线段树上维护即可。
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)
namespace xin_io
{
#define debug cout<<"debug"<<endl
#define enum(x) cout<<#x" = "<<x<<endl;
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &x)
{
register type s = 0; register int f = 1; register char ch = gc();
while(!isdigit(ch)) {if(ch == ‘-‘) f = -1; ch = gc();}
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return x = s * f,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7,mod = 998244353; const ll llinf = 1e18+7;
#define int long long
namespace xin
{
class xin_edge{public:int w,next,ver;}edge[maxn];
int head[maxn],zhi = 0;
inline void add(int x,int y,int z) {edge[++zhi].ver = y; edge[zhi].w = z; edge[zhi].next = head[x]; head[x] = zhi;}
class xin_seg
{
private:
#define ls(fa) (fa << 1)
#define rs(fa) (fa << 1 | 1)
inline void up(int fa) {t[fa].s = t[ls(fa)].s + t[rs(fa)].s;}
inline void down(int fa,int l,int r)
{
if(!t[fa].debt) return ;
register int mid = l + r >> 1;
t[ls(fa)].s += t[fa].debt * (mid - l + 1); t[rs(fa)].s += t[fa].debt * (r - mid);
t[ls(fa)].debt += t[fa].debt; t[rs(fa)].debt += t[fa].debt;
t[fa].debt = 0;
}
public:
class xin_tree{public:int s,debt;}t[maxn * 4];
void update(int fa,int l,int r,int ql,int qr,int val)
{
if(ql <= l and qr >= r) return t[fa].s += (r - l + 1) * val,t[fa].debt += val,void();
register int mid = l + r >> 1;
down(fa,l,r);
if(ql <= mid) update(ls(fa),l,mid,ql,qr,val);
if(qr > mid) update(rs(fa),mid+1,r,ql,qr,val);
up(fa);
}
int query(int fa,int l,int r,int pos)
{
if(l == r) return t[fa].s;
register int mid = l + r >> 1,ret = 0; down(fa,l,r);
if(pos <= mid) ret += query(ls(fa),l,mid,pos);
else ret += query(rs(fa),mid+1,r,pos);
return ret;
}
}t;
int n,qnum,fa[maxn];
int in[maxn],out[maxn],tot = 0,d[maxn],sum[maxn],w[maxn];
void xt(int x)
{
in[x] = ++tot; d[x] = d[fa[x]] + 1;
asm(i,x)
{
register int y = edge[i].ver;
sum[y] = w[y] - sum[x];
xt(y);
}
out[x] = tot;
}
inline short main()
{
io >> n >> qnum;
try(i,2,n)
{
io >> fa[i] >> w[i];
add(fa[i],i,w[i]);
}
xt(1);
try(i,1,qnum)
{
register int op; io >> op;
if(op & 1)
{
register int x,y,z; io >> x >> y >> z;
register int p1 = t.query(1,1,n,in[x]),p2 = t.query(1,1,n,in[y]);
if(!(d[x] & 1)) p1 = -p1; if(!(d[y] & 1)) p2 = -p2;
register int ret1 = sum[x] + p1,ret2 = sum[y] + p2;
if((d[x] & 1) and (d[y] & 1))
{
if((z - ret1 - ret2) & 1) puts("none");
else printf("%lld\n",(z - ret1 - ret2) >> 1);
}
else if(!(d[x] & 1) and !(d[y] & 1))
{
if((ret1 + ret2 - z) & 1) puts("none");
else printf("%lld\n",(ret1 + ret2 - z) >> 1);
}
else
{
if(ret1 + ret2 == z) puts("inf");
else puts("none");
}
}
else
{
register int x,z; io >> x >> z;
register int p = z - w[x];
w[x] = z;
if(!(d[x] & 1)) p = -p;
t.update(1,1,n,in[x],out[x],p);
}
}
return 0;
}
}
signed main() {return xin::main();}
Rectangle
首先第一思路就是拿四个线卡来卡去。
然后就是 \(n^4\)
可以拿二十多分。。
正解实际上是先拿两条线。
之后发现答案贡献与两条线之间的 \(y\) 有关，所以用树状数组来维护 \(\sum y\)
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)
namespace xin_io
{
#define debug cout<<"debug"<<endl
#define enum(x) cout<<#x" = "<<x<<endl;
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &x)
{
register type s = 0; register int f = 1; register char ch = gc();
while(!isdigit(ch)) {if(ch == ‘-‘) f = -1; ch = gc();}
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return x = s * f,*this;
}}io;
}
using namespace xin_io; static const int maxn = 2500+10,inf = 1e9+7,mod = 1e9+7; const ll llinf = 1e18+7;
namespace xin
{
#define int long long
int n;
class xin_bit
{
private:
#define lowbit(x) (x & -x)
public:
int c[2][maxn][maxn];
inline void plus(int id,int k,int x,int val)
{
for(int i=x;i<=2500;i+=lowbit(i))
c[id][k][i] += val;
}
inline int query(int id,int k,int x)
{
register int ret = 0;
for(int i=x;i;i-=lowbit(i)) ret += c[id][k][i];
return ret;
}
}bit;
int a[maxn][maxn],ans;
bool vis[maxn][maxn];
inline short main()
{
io >> n;
try(i,1,n)
{
register int x,y; io >> x >> y;
a[x][++a[x][0]] = y;
}
try(i,1,2500)
{
std::sort(a[i]+1,a[i]+a[i][0]+1);
a[i][a[i][0]+1] = 2501;
}
try(i,1,2500)
{
if(!a[i][0]) continue;
try(j,1,a[i][0])
if(!vis[i][a[i][j]])
{
vis[i][a[i][j]] = 1;
bit.plus(1,i,a[i][j],1);
bit.plus(0,i,a[i][j],a[i][j]);
}
throw(j,i-1,1)
{
if(!a[j][0]) continue;
register int l1 = 1,l2 = 1;
try(k,1,a[j][0])
if(!vis[i][a[j][k]])
{
vis[i][a[j][k]] = 1;
bit.plus(1,i,a[j][k],1);
bit.plus(0,i,a[j][k],a[j][k]);
}
register int temp = std::max(a[i][1],a[j][1]);
while(a[i][l1+1] <= temp) l1 ++; while(a[j][l2+1]<=temp) l2 ++;
while(l1 <= a[i][0] and l2 <= a[j][0])
{
register int zhuan = std::min(a[i][l1+1],a[j][l2+1]);
int ret1 = (bit.query(0,i,zhuan-1)-bit.query(0,i,temp-1));
int ret2 = (bit.query(1,i,zhuan-1)-bit.query(1,i,temp-1));
//enum(ret1); enum(ret2);
ans=(ans+(i-j)*(ret1*bit.query(1,i,std::min(a[i][l1],a[j][l2]))-(ret2*bit.query(0,i,std::min(a[i][l1],a[j][l2])))))%mod;
temp = zhuan;
if(a[i][l1+1] <= temp) l1 ++; if(a[j][l2+1] <= temp) l2 ++;
}
}
}
cout<<ans<<endl;
return 0;
}
}
signed main() {return xin::main();}