备用库
Komorebi_shine · · 个人记录
test3
//path
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010;
const int M = 5000010;
const int B = 17;
int _w;
int read() {
int x = 0, ch;
while( isspace(ch = getchar()) );
do x = x * 10 + ch - '0';
while( isdigit(ch = getchar()) );
return x;
}
int n, m, C, s, t;
namespace G {
int head[N], nxt[M], to[M], len[M], eid;
void init() {
eid = 0;
memset(head, -1, sizeof head);
}
void link( int u, int v, int w ) {
len[eid] = w, to[eid] = v;
nxt[eid] = head[u], head[u] = eid++;
}
}
struct Node {
int u, d;
Node() {}
Node( int u, int d ):
u(u), d(d) {}
bool operator<( const Node &rhs ) const {
return d > rhs.d;
}
};
priority_queue<Node> pq;
int dis[N], done[N];
void dijkstra() {
using namespace G;
memset(dis, 0x3f, sizeof dis);
dis[s] = 0, pq.push( Node(s, 0) );
while( !pq.empty() ) {
Node o = pq.top(); pq.pop();
int u = o.u;
if( done[u] ) continue;
done[u] = 1;
for( int i = head[u]; ~i; i = nxt[i] ) {
int v = to[i], w = len[i];
if( dis[u] + w < dis[v] ) {
dis[v] = dis[u] + w;
pq.push( Node(v, dis[v]) );
}
}
}
printf( "%d\n", dis[t] );
}
int main() {
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
n = read(), m = read(), C = read();
G::init();
for( int i = 0; i < m; ++i ) {
int u = read(), v = read(), w = read();
G::link(u, v, w);
}
for( int i = 0; i < (1<<B); ++i )
for( int j = 0; j < B; ++j ) {
int v = i ^ (1<<j);
G::link(i, v, (1<<j)*C);
}
s = read(), t = read();
dijkstra();
return 0;
}
//interval
#include <cstring>
#include <algorithm>
#include <cstdio>
typedef long long ll;
const int N = 200010;
const ll INFLL = 3e18;
int _w;
int n, k, a[N];
ll ans;
int right[N];
void prelude() {
for( int i = n; i >= 1; --i )
if( a[i] == 1 )
right[i] = a[i+1] == 1 ? right[i+1] : i;
}
bool check( ll a, ll b ) {
return 1.0 * a * b <= INFLL;
}
ll solve( int L ) {
ll p = 1, s = 0, ans = 0;
for( int i = L; i <= n; ++i )
if( a[i] == 1 ) {
int R = right[i];
int cnt = R-i+1;
if( p % k == 0 ) {
ll tmp = p/k-s;
if( tmp >= 1 && tmp <= cnt )
++ans;
}
i = R, s += cnt;
} else {
if( !check(p, a[i]) ) break;
p *= a[i], s += a[i];
if( p % k == 0 && p/k == s )
++ans;
}
return ans;
}
int main() {
freopen("interval.in", "r", stdin);
freopen("interval.out", "w", stdout);
_w = scanf( "%d%d", &n, &k );
for( int i = 1; i <= n; ++i )
_w = scanf( "%d", a+i );
prelude();
for( int i = 1; i <= n; ++i )
ans += solve(i);
printf( "%lld\n", ans );
return 0;
}
//group
#include <iostream>
#include <cstdio>
const int N = 505;
const int M = N * N;
bool vis[N] , col[N] , f[N];
int tov[M] , nxt[M];
bool want[N][N];
int last[N];
int cnt[2];
int n , m , tot , ans;
int iabs(int x){return x > 0 ? x : -x;}
void insert(int x , int y){tov[++ tot] = y , nxt[tot] = last[x] , last[x] = tot;}
void dfs(int x , bool c = 0)
{
if (vis[x])
{
if (col[x] ^ c) ans = -1;
return;
}
vis[x] = 1 , ++ cnt[col[x] = c];
for (int i = last[x];~ans && i;i = nxt[i]) dfs(tov[i] , c ^ 1);
}
int main()
{
freopen("group.in" , "r" , stdin) , freopen("group.out" , "w" , stdout);
scanf("%d%d" , &n , &m);
for (int i = 1 , x , y;i <= m;++ i) scanf("%d%d" , &x , &y) , want[x][y] = want[y][x] = 1;
for (int x = 1;x < n;++ x)
for (int y = x + 1;y <= n;++ y)
if (!want[x][y] || !want[y][x])
insert(x , y) , insert(y , x);
ans = n , f[0] = 1;
for (int x = 1;~ans && x <= n;++ x)
if (!vis[x])
{
cnt[0] = cnt[1] = 0 , dfs(x);
for (int i = n;i >= 0;-- i) f[i] = (i >= cnt[0] ? f[i - cnt[0]] : 0) | (i >= cnt[1] ? f[i - cnt[1]]: 0);
}
for (int i = 0;i <= n;++ i) if (f[i]) ans = std::min(ans , iabs(n - (i << 1)));
if (~ans) printf("%d\n" , ans);
else printf("No Answer\n");
fclose(stdin) , fclose(stdout);
return 0;
}test4
//pyramid
#include <iostream>
#include <cstdio>
const int N = 1005;
std::pair<std::pair<int , int> , int> smin[N][N];
std::pair<std::pair<int , int> , int> que[N];
int num[N][N] , sum[N][N];
int head , tail , n , m , row , col , row_ , col_ , ans;
std::pair<std::pair<int , int> , std::pair<int , int> > loc;
int calc_sum(int x , int y , int r , int c){return sum[x + r - 1][y + c - 1] - sum[x - 1][y + c - 1] - sum[x + r - 1][y - 1] + sum[x - 1][y - 1];}
std::pair<int , int> swift(std::pair<int , int> pr){return std::make_pair(pr.second , pr.first);}
void add(std::pair<std::pair<int , int> , int> pr)
{
for (;head <= tail && que[tail].second >= pr.second;-- tail);
que[++ tail] = pr;
}
std::pair<std::pair<int , int> , int> query(int lim)
{
for (;head <= tail && que[head].first.first < lim;++ head);
return que[head];
}
void update(std::pair<int , int> loc1 , std::pair<std::pair<int , int> , int> ret)
{
int cur = calc_sum(loc1.first , loc1.second , row , col) - ret.second;
if (cur > ans) ans = cur , loc.first = loc1 , loc.second = swift(ret.first);
}
int main()
{
freopen("pyramid.in" , "r" , stdin) , freopen("pyramid.out" , "w" , stdout);
scanf("%d%d%d%d%d%d" , &m , &n , &col , &row , &col_ , &row_);
for (int i = 1;i <= n;++ i)
for (int j = 1;j <= m;++ j)
scanf("%d" , &num[i][j]) , sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + num[i][j] , smin[i][j] = std::make_pair(std::make_pair(i , j) , 200000000);
for (int j = 1 , width = row - 2 - row_ + 1;j <= m - col_ + 1;++ j)
{
head = 1 , tail = 0;
for (int i = 1;i < width;++ i) add(std::make_pair(std::make_pair(i , j) , calc_sum(i , j , row_ , col_)));
for (int i = width;i <= n - row_ + 1;++ i)
{
add(std::make_pair(std::make_pair(i , j) , calc_sum(i , j , row_ , col_)));
smin[i - width + 1][j] = query(i - width + 1);
}
}
for (int i = 1 , width = col - 2 - col_ + 1;i <= n - row + 1;++ i)
{
head = 1 , tail = 0;
for (int j = 2;j < width + 1;++ j) add(std::make_pair(swift(smin[i + 1][j].first) , smin[i + 1][j].second));
for (int j = col , j_;j <= m;++ j)
{
j_ = j - col + 1 + width;
add(std::make_pair(swift(smin[i + 1][j_].first) , smin[i + 1][j_].second));
update(std::make_pair(i , j - col + 1) , query(j - col + 2));
}
}
printf("%d\n" , ans);
// printf("%d %d\n" , loc.first.second , loc.first.first);
// printf("%d %d\n" , loc.second.second , loc.second.first);
fclose(stdin) , fclose(stdout);
return 0;
}
//forest
#include <utility>
#include <cstdio>
const int P = 1000000007;
const int N = 100005;
const int M = N << 1;
const int LGN = 17;
typedef std::pair<int , int> seg;
int up[N] , LOG[N] , fa[N] , val[N] , last[N] , ans[N] , depth[N] , del[N];
int tov[M] , nxt[M];
seg res[N] , edg[N];
int anc[N][LGN];
int n , tot;
int quick_power(int x , int y)
{
int ret = 1;
for (;y;y >>= 1 , x = 1ll * x * x % P) if (y & 1) ret = 1ll * ret * x % P;
return ret;
}
int inv(int x){return quick_power(x , P - 2);}
void link(int x , int y){tov[++ tot] = y , nxt[tot] = last[x] , last[x] = tot;}
void dfs(int x)
{
for (int i = last[x] , y;i;i = nxt[i])
if ((y = tov[i]) != anc[x][0])
anc[y][0] = x , up[y] = up[x] + val[y] , depth[y] = depth[x] + 1 , dfs(y);
}
void pre()
{
LOG[1] = 0;
for (int i = 2;i <= n;++ i) LOG[i] = LOG[i - 1] + (1 << LOG[i - 1] + 1 == i);
for (int i = 1;i <= LOG[n];++ i)
for (int x = 1;x <= n;++ x)
anc[x][i] = anc[anc[x][i - 1]][i - 1];
}
int adjust(int x , int d)
{
for (int i = LOG[depth[x]];i >= 0;-- i)
if (depth[anc[x][i]] >= d) x = anc[x][i];
return x;
}
int lca(int x , int y)
{
if (depth[x] > depth[y]) std::swap(x , y);
y = adjust(y , depth[x]);
if (x == y) return x;
for (int i = LOG[depth[x]];i >= 0;-- i)
if (anc[x][i] != anc[y][i])
x = anc[x][i] , y = anc[y][i];
return anc[x][0];
}
int dist(int x , int y)
{
int z = lca(x , y);
return up[x] + up[y] - up[z] - up[anc[z][0]];
}
int dist(const seg &l){return dist(l.first , l.second);}
int getfather(int son){return fa[son] == son ? son : fa[son] = getfather(fa[son]);}
void update(seg &l , int &d , const seg &l_)
{
int d_ = dist(l_);
if (d < d_) d = d_ , l = l_;
}
void merge(int x , int y)
{
x = getfather(x) , y = getfather(y);
if (x == y) return;
fa[y] = x;int d = dist(res[x]);
int u = res[x].first , v = res[x].second;
update(res[x] , d , res[y]);
update(res[x] , d , std::make_pair(u , res[y].first));
update(res[x] , d , std::make_pair(u , res[y].second));
update(res[x] , d , std::make_pair(v , res[y].first));
update(res[x] , d , std::make_pair(v , res[y].second));
}
int main()
{
freopen("forest.in" , "r" , stdin) , freopen("forest.out" , "w" , stdout);
scanf("%d" , &n);
int cur = 1;
for (int x = 1;x <= n;++ x) scanf("%d" , &val[x]) , fa[x] = x , res[x] = std::make_pair(x , x) , cur = 1ll * cur * val[x] % P;
for (int i = 1 , x , y;i < n;++ i) scanf("%d%d" , &x , &y) , link(x , y) , link(y , x) , edg[i] = std::make_pair(x , y);
depth[1] = 1 , up[1] = val[1] , dfs(1) , pre();
for (int i = 1;i < n;++ i) scanf("%d" , &del[i]);
for (int i = n - 1 , x , y;i >= 1;-- i)
{
ans[i] = cur , x = getfather(edg[del[i]].first) , y = getfather(edg[del[i]].second);
cur = 1ll * cur * inv(dist(res[x])) % P * inv(dist(res[y])) % P;
merge(x , y) , cur = 1ll * cur * dist(res[getfather(x)]) % P;
}
ans[0] = cur;
for (int i = 0;i < n;++ i) printf("%d\n" , ans[i]);
fclose(stdin) , fclose(stdout);
return 0;
}
//guess
#include <algorithm>
#include <iostream>
#include <cstdio>
const int N = 1005;
const int M = N * N;
struct edge
{
int x , y , len;
inline edge(int x_ = 0 , int y_ = 0 , int len_ = 0) : x(x_) , y(y_) , len(len_) {}
inline bool operator<(const edge e)const{return len < e.len;}
}e[M];
int fa[N];
int n , m , ans;
int getfather(int son){return fa[son] == son? son : fa[son] = getfather(fa[son]);}
void Kruskal()
{
std::sort(e + 1 , e + 1 + m);
ans = 0;
for (int i = 1 , fx , fy;i <= m;++ i)
{
fx = getfather(e[i].x) , fy = getfather(e[i].y);
if (fx == fy) continue;
fa[fy] = fx , ans += e[i].len;
}
}
int main()
{
freopen("guess.in" , "r" , stdin) , freopen("guess.out" , "w" , stdout);
scanf("%d" , &n);
for (int i = 1;i <= n;++ i)
for (int j = i , x;j <= n;++ j)
scanf("%d" , &x) , e[++ m] = edge(i - 1 , j , x);
for (int x = 0;x <= n;++ x) fa[x] = x;
Kruskal() , printf("%d\n" , ans);
fclose(stdin) , fclose(stdout);
return 0;
}test5
//sort
#include <bits/stdc++.h>
const int N = 100005;
const int C = 26;
struct data
{
int cnt[C];
data(){for (int c = 0;c < C;++ c) cnt[c] = 0;}
data operator+(const data &d)
{
data ret;
for (int c = 0;c < C;++ c) ret.cnt[c] = cnt[c] + d.cnt[c];
return ret;
}
data &operator+=(const data &d)
{
for (int c = 0;c < C;++ c) cnt[c] += d.cnt[c];
return *this;
}
};
char tg[N << 2];
data t[N << 2];
char str[N];
int n , q;
void build(int x , int l , int r)
{
tg[x] = '#';
if (l == r)
{
++ t[x].cnt[str[l] - 'a'];
return;
}
int mid = l + r >> 1;
build(x << 1 , l , mid) , build(x << 1 | 1 , mid + 1 , r) , t[x] = t[x << 1] + t[x << 1 | 1];
}
void fillc(int x , int l , int r , char tg_)
{
tg[x] = tg_;
for (int c = 0;c < C;++ c) t[x].cnt[c] = (c == tg_ - 'a') * (r - l + 1);
}
void clear(int x , int l , int r)
{
if (l == r) return;
int mid = l + r >> 1;
if (tg[x] != '#')
{
fillc(x << 1 , l , mid , tg[x]) , fillc(x << 1 | 1 , mid + 1 , r , tg[x]);
tg[x] = '#';
}
}
void count(int x , int st , int en , int l , int r , data &d)
{
if (st > en) return;
if (st == l && en == r)
{
d += t[x];
return;
}
clear(x , l , r);
int mid = l + r >> 1;
if (en <= mid) count(x << 1 , st , en , l , mid , d);
else if (mid + 1 <= st) count(x << 1 | 1 , st , en , mid + 1 , r , d);
else count(x << 1 , st , mid , l , mid , d) , count(x << 1 | 1 , mid + 1 , en , mid + 1 , r , d);
}
void fillc(int x , int st , int en , int l , int r , int c)
{
if (st > en) return;
if (st == l && en == r)
{
fillc(x , l , r , 'a' + c);
return;
}
clear(x , l , r);
int mid = l + r >> 1;
if (en <= mid) fillc(x << 1 , st , en , l , mid , c);
else if (mid + 1 <= st) fillc(x << 1 | 1 , st , en , mid + 1 , r , c);
else fillc(x << 1 , st , mid , l , mid , c) , fillc(x << 1 | 1 , mid + 1 , en , mid + 1 , r , c);
t[x] = t[x << 1] + t[x << 1 | 1];
}
void display(int x , int l , int r)
{
if (l == r)
{
for (int c = 0;c < C;++ c)
if (t[x].cnt[c]) putchar('a' + c);
return;
}
clear(x , l , r);
int mid = l + r >> 1;
display(x << 1 , l , mid) , display(x << 1 | 1 , mid + 1 , r);
}
int main()
{
freopen("sort.in" , "r" , stdin) , freopen("sort.out" , "w" , stdout);
scanf("%d%d" , &n , &q);
scanf("%s" , str + 1);
build(1 , 1 , n);
for (int i = 1 , l , r , x;i <= q;++ i)
{
scanf("%d%d%d" , &l , &r , &x);
data tmp;
count(1 , l , r , 1 , n , tmp);
if (x == 1)
for (int c = 0;c < C;++ c)
{
fillc(1 , l , l + tmp.cnt[c] - 1 , 1 , n , c);
l += tmp.cnt[c];
}
else
for (int c = 0;c < C;++ c)
{
fillc(1 , r - tmp.cnt[c] + 1 , r , 1 , n , c);
r -= tmp.cnt[c];
}
}
display(1 , 1 , n) , putchar('\n');
fclose(stdin) , fclose(stdout);
return 0;
}
//friend
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
typedef long long LL;
int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch))
{
if (ch=='-')
f=-1;
ch=getchar();
}
while (isdigit(ch))
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=300500;
struct D
{
int mx,l,r;
LL sum;
};
D operator+(D x,D y)
{
D ret;
ret.sum=x.sum+y.sum;
ret.l=x.l,ret.r=y.r;
ret.mx=y.mx;
return ret;
}
struct segment_tree
{
int tag[N<<2];
D v[N<<2];
void S(int x,int y)
{
if (tag[x])
tag[x]=min(tag[x],y);
else
tag[x]=y;
v[x].sum=1ll*y*(v[x].r-v[x].l+1);
v[x].mx=y;
}
void clear(int x)
{
if (v[x].l==v[x].r)
return;
if (tag[x])
{
S(x<<1,tag[x]),S(x<<1|1,tag[x]);
tag[x]=0;
}
}
void update(int x)
{
v[x]=v[x<<1]+v[x<<1|1];
}
void build(int x,int l,int r)
{
if (l==r)
{
v[x].l=l,v[x].r=r;
v[x].sum=l;
v[x].mx=l;
tag[x]=0;
return;
}
int mid=l+r>>1;
build(x<<1,l,mid),build(x<<1|1,mid+1,r);
update(x);
}
int search(int x,int y,int l,int r)
{
clear(x);
if (l==r)
if (v[x].mx>y)
return l;
else
return 0;
int mid=l+r>>1;
if (v[x<<1].mx>y)
return search(x<<1,y,l,mid);
else
return search(x<<1|1,y,mid+1,r);
}
void set(int x,int st,int en,int l,int r,int edit)
{
clear(x);
if (st==l&&en==r)
{
S(x,edit);
return;
}
int mid=l+r>>1;
if (en<=mid)
set(x<<1,st,en,l,mid,edit);
else
if (mid+1<=st)
set(x<<1|1,st,en,mid+1,r,edit);
else
set(x<<1,st,mid,l,mid,edit),set(x<<1|1,mid+1,en,mid+1,r,edit);
update(x);
}
}t;
LL last;
int n,m;
int main()
{
freopen("friend.in","r",stdin);
freopen("friend.out","w",stdout);
n=read(),m=read();
t.build(1,1,n);
last=t.v[1].sum;
for (int i=1;i<=m;i++)
{
int l=read(),r=read();
int p=t.search(1,l,1,n);
if (l<=p&&p<=r)
t.set(1,p,r,1,n,l);
LL ans=last-t.v[1].sum;
printf("%lld\n",ans);
last=t.v[1].sum;
}
fclose(stdin);
fclose(stdout);
return 0;
}
//sequence
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N=1005;
const int L=14;
const int C=N*L/2;
const int S=3500;
const int P=67;
const int A=1<<L;
int pre[N][N],suf[N][N],tot[N];
int per[N],rem[N],pos[N],p[N];
bool exist[N],used[N];
int f[S][C];
int id[A];
int n,K,cnt,l,cur;
LL ans;
int lowbit(int x){return x&-x;}
int bitcount(int s)
{
int ret=0;
for (;s;s-=lowbit(s)) ++ret;
return ret;
}
void prepare()
{
for (int i=1;i<=n;++i)
{
for (int j=1;j<=n;++j) pre[i][j]=pre[i-1][j];
if (per[i]) ++pre[i][per[i]];
}
for (int i=1;i<=n;++i)
for (int j=n;j>=1;--j)
pre[i][j]+=pre[i][j+1];
for (int i=n;i>=1;--i)
{
for (int j=1;j<=n;++j) suf[i][j]=suf[i+1][j];
if (per[i]) ++suf[i][per[i]];
}
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
suf[i][j]+=suf[i][j-1];
for (int i=1;i<=n;++i)
if (per[i]) cur+=pre[i][per[i]+1];
l=pos[0]/2;
for (int s=0;s<1<<pos[0];++s)
if (bitcount(s)==pos[0]-l)
id[s]=++cnt;
}
int tmp[20],rec[20];
void load(int curr)
{
int s=0;
for (int i=l+1;i<=pos[0];++i) s|=1<<p[i]-1;
int sid=id[s],ret=curr;
for (int i=l+1;i<=pos[0];++i) ret+=pre[pos[i]][rem[p[i]]+1]+suf[pos[i]][rem[p[i]]-1];
tmp[0]=0,rec[0]=0;
for (int i=1;i<=pos[0];++i)
if (!((s>>i-1)&1)) tmp[++tmp[0]]=rem[i];
else rec[++rec[0]]=rem[i];
sort(tmp+1,tmp+1+tmp[0]),sort(rec+1,rec+1+rec[0]);
for (int i=1,ptr=1;i<=rec[0];++i)
{
for (;ptr<=tmp[0]&&tmp[ptr]<rec[i];++ptr);
ret+=tmp[0]+1-ptr;
}
++f[sid][ret];
}
void dfs(int x,int curr)
{
if (x==pos[0]+1)
{
load(curr);
return;
}
int total=0;
for (int i=1;i<=rem[0];++i)
if (!used[i]) used[i]=1,p[x]=i,dfs(x+1,curr+x-l-1-total),used[i]=0;
else ++total;
}
void solve(int curr)
{
int s=0;
for (int i=1;i<=l;++i) s|=1<<p[i]-1;
int sid=id[((1<<pos[0])-1)^s],ret=curr;
for (int i=1;i<=l;++i) ret+=pre[pos[i]][rem[p[i]]+1]+suf[pos[i]][rem[p[i]]-1];
if (K-cur-ret>=0&&K-cur-ret<=n*(pos[0]-l)) ans+=f[sid][K-cur-ret];
}
void calc(int x,int curr)
{
if (x==l+1)
{
solve(curr);
return;
}
int total=0;
for (int i=1;i<=rem[0];++i)
if (!used[i]) used[i]=1,p[x]=i,calc(x+1,curr+x-1-total),used[i]=0;
else ++total;
}
int main()
{
freopen("sequence.in","r",stdin),freopen("sequence.out","w",stdout);
scanf("%d%d",&n,&K);
for (int i=1;i<=n;++i)
{
scanf("%d",&per[i]);
if (!per[i]) pos[++pos[0]]=i;
else exist[per[i]]=1;
}
for (int i=1;i<=n;++i) if (!exist[i]) rem[++rem[0]]=i;
prepare(),dfs(l+1,0),calc(1,0);
printf("%lld\n",ans);
fclose(stdin),fclose(stdout);
return 0;
}