难度:☆☆☆☆☆☆☆

/*二分答案算斜率算截距巴拉巴拉很好推的公式貌似没这么麻烦我太弱了......唉不重要...*/#include
     
      #include
      
       #include
       
        #include
        
         #define N 100007using namespace std;int n,m,cnt;int X[N],Y[N];double k,x,y,b,dis2;struct segment{    double k,b;}e[N<<1];inline int read(){    int x=0,f=1;char c=getchar();    while(c>'9'||c<'0'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}double work(double x,double y){    return sqrt(double(x)*double(x)+double(y)*double(y));}int main(){    freopen("geometry.in","r",stdin);    freopen("geometry.out","w",stdout);    n=read();    for(int i=1;i<=n;i++) X[i]=read();    for(int i=1;i<=n;i++) Y[i]=read();    sort(X+1,X+n+1);sort(Y+1,Y+n+1);    for(int i=1;i<=n;i++)    {        e[i].k=double(Y[i])/-double(X[i]);        e[i].b=Y[i];     }    m=read();    for(int i=1;i<=m;i++)    {        x=read();y=read();cnt=0;        if(x==0)        {            int l=1,r=n,mid;            while(l<=r)            {                mid=l+r>>1;                if(Y[mid]>=y) cnt=mid,l=mid+1;                else r=mid-1;            }         }        double dis1=work(double(x),double(y));        k=double(y)/double(x);        int l=1,r=n,mid;        while(l<=r)        {            mid=l+r>>1;            if(work(double(e[mid].b/(k-e[mid].k)),k*double(e[mid].b/(k-e[mid].k)))<=dis1)              cnt=mid,l=mid+1;            else r=mid-1;        }        printf("%d\n",cnt);    }    fclose(stdin);fclose(stdout);    return 0;}
        
       
      
     

 

/*貌似数据水，贪心能贪70分...差分约束做法记录前缀和S[i],i>=8时首先要满足条件 s[i]-s[i-8]>=a[i]0<=s[i]-s[i-1]<=b[i]当i<8时有s[23]-s[16+i]+s[i]>=a[i]    因为第三个式子不满足差分约束形式，可以看出s[23]有单调性，可以二分…所以可以二分答案当常量处理 Spfa负环则无解还有一种网络流做法，表示很懵逼。*/#include
     
      #include
      
       #include
       
        #include
        
         #define N 33using namespace std;int n,m,ans,cnt;int head[N<<1],dis[N],a[N],b[N];bool inq[N];struct edge{    int u,v,dis,net;}e[N<<1];inline void add(int u,int v,int w){    e[++cnt].v=v;e[cnt].net=head[u];e[cnt].dis=w;head[u]=cnt;}inline int read(){    int x=0,f=1;char c=getchar();    while(c>'9'||c<'0'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}bool spfa(){    queue
         
          q;    memset(dis,-0x7f7f7f,sizeof dis);    memset(inq,0,sizeof inq);    dis[0]=0;inq[0]=1;q.push(0);    while(!q.empty())    {        int u=q.front();q.pop();inq[u]=0;        if(dis[u]>1000) return false;        for(int i=head[u];i;i=e[i].net)        {            int v=e[i].v;            if(dis[v]
          
           1000) { ans=-1;break; } if(solve(ans)) break; } printf("%d\n",ans); } return 0;}
          
         
        
       
      
     

 

线段树

部分分可以dp f[i][j]表示前i个数选了j个的答案

f[i][j]=f[i-1][j]+f[i-1][j-1]*a[i] (i选不选)

k=1时线段树区间求和区间修改，我只会这个....

 

线段树区间合并操作。

k比较小，所以线段树每个节点维护一个区间答案记为f[i]

考虑一段区间i,左边取j个右边就取i-j个 答案是每个方案的左边乘右边的和。

就是i左儿子f[j]和右边的f[i-j] 所以f[i]=Σ(j=0~i) lc f[j]*rc f[i-j]

考虑取反操作，i是奇数就取反，偶数无影响(因为是相乘)

考虑区间加， 开始f[i] 是 a1*a2……an  后来是(a1+c)*(a2+c)……(an+c)

考虑类似二项式定理,当上述a1~an  n个方案如果取了j个了，分别为al1,al2……alj

那考虑最后答案，如果已经选了j个方案是(al1+c)(al2+c)……(alj+c)再还能选i-j个 最后答案是C(len-i,i-j)*f[j]*c^(i-j)

复杂度 O(k^2*nlogn)

 

只懂思路，代码....果断粘std

 

#include 
     
      #include 
      
       #define MOD 1000000007#define N 100005typedef long long LL;using namespace std;struct Node{	LL f[11];} node[N * 4];LL a[N], lazy1[N * 4];bool lazy2[N * 4];LL C[N][11];Node merge(Node lc, Node rc){	Node o;	o.f[0] = 1;	for (int i = 1; i <= 10; i++)	{		o.f[i] = 0;		for (int j = 0; j <= i; j++)			o.f[i] = (o.f[i] + lc.f[j] * rc.f[i - j] % MOD) % MOD;	}	return o;}void build(int o, int l, int r){	if (l == r)	{		for (int i = 0; i <= 10; i++) node[o].f[i] = 0;		node[o].f[0] = 1;		node[o].f[1] = (a[l] % MOD + MOD) % MOD;		return ;	}	int mid = (l + r) >> 1;	build(o * 2, l, mid);	build(o * 2 + 1, mid + 1, r);	node[o] = merge(node[o * 2], node[o * 2 + 1]);	return ;}void update1(int o, int l, int r, int c){	int len = r - l + 1;	LL ff[11];	for (int i = 0; i <= 10; i++) ff[i] = node[o].f[i];	for (int i = 1; i <= 10; i++)	{		node[o].f[i] = 0;		LL t = 1;		for (int j = 0; j <= i; j++)		{			LL tmp = ff[i - j] * C[len - (i - j)][j] % MOD * t % MOD;			node[o].f[i] = (node[o].f[i] + tmp) % MOD;			t = t * c % MOD;		}	}	return ;}void push_down(int o, int l, int r){	int mid = (l + r) >> 1;	if (lazy1[o])	{		if (lazy2[o * 2])			lazy1[o * 2] = (lazy1[o * 2] + MOD - lazy1[o]) % MOD;		else			lazy1[o * 2] = (lazy1[o * 2] + lazy1[o]) % MOD;		if (lazy2[o * 2 + 1])			lazy1[o * 2 + 1] = (lazy1[o * 2 + 1] + MOD - lazy1[o]) % MOD;		else			lazy1[o * 2 + 1] = (lazy1[o * 2 + 1] + lazy1[o]) % MOD;		update1(o * 2, l, mid, lazy1[o]);		update1(o * 2 + 1, mid + 1, r, lazy1[o]);		lazy1[o] = 0;	}	if (lazy2[o])	{		lazy2[o * 2] ^= 1;		lazy2[o * 2 + 1] ^= 1;		for (int j = 1; j <= 10; j += 2)		{			node[o * 2].f[j] = MOD - node[o * 2].f[j];			node[o * 2 + 1].f[j] = MOD - node[o * 2 + 1].f[j];		}		lazy2[o] = 0;	}}void modify1(int o, int l, int r, int ll, int rr, int c){	if (ll <= l && rr >= r)	{		if (lazy2[o]) lazy1[o] = (lazy1[o] + MOD - c) % MOD;		else lazy1[o] = (lazy1[o] + c) % MOD;		update1(o, l, r, c);		return ;	}	int mid = (l + r) >> 1;	push_down(o, l, r);	if (ll <= mid) modify1(o * 2, l, mid, ll, rr, c);	if (rr > mid) modify1(o * 2 + 1, mid + 1, r, ll, rr, c);	node[o] = merge(node[o * 2], node[o * 2 + 1]);	return ;}void modify2(int o, int l, int r, int ll, int rr){	if (ll <= l && rr >= r)	{		for (int i = 1; i <= 10; i += 2) node[o].f[i] = MOD - node[o].f[i];		lazy2[o] ^= 1;		return ;	}	int mid = (l + r) >> 1;	push_down(o, l, r);	if (ll <= mid) modify2(o * 2, l, mid, ll, rr);	if (rr > mid) modify2(o * 2 + 1, mid + 1, r, ll, rr);	node[o] = merge(node[o * 2], node[o * 2 + 1]);	return ;}Node query(int o, int l, int r, int ll, int rr){	if (ll <= l && rr >= r)		return node[o];	int mid = (l + r) >> 1;	push_down(o, l, r);	if (rr <= mid) return query(o * 2, l, mid, ll, rr);	if (ll > mid) return query(o * 2 + 1, mid + 1, r, ll, rr);	Node lc = query(o * 2, l, mid, ll, rr);	Node rc = query(o * 2 + 1, mid + 1, r, ll, rr);	return merge(lc, rc);}int main(int argc, char ** argv){	freopen("game.in", "r", stdin);	freopen("game.out", "w", stdout);	int n, m;	scanf("%d %d", &n, &m);	C[0][0] = 1;	for (int i = 1; i <= n; i++)	{		C[i][0] = 1;		for (int j = 1; j <= 10; j++)			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;	}	for (int i = 1; i <= n; i++)		scanf("%d", &a[i]);	build(1, 1, n);	for (int i = 1; i <= m; i++)	{		int l, r, opt;		scanf("%d%d%d",&opt, &l, &r);		if (opt == 1)		{			int c;			scanf("%d", &c);			c = (c % MOD + MOD) % MOD;			modify1(1, 1, n, l, r, c);		}		else if (opt == 2)		{			modify2(1, 1, n, l, r);		}		else		{			int k;			scanf("%d", &k);			Node o = query(1, 1, n, l, r);			printf("%d\n", o.f[k] % MOD);		}	}	return 0;}